19332번 - Prefix-free Queries 다국어

Let $C (s_1, s_2, \ldots, s_k)$ be the number of ways to construct a prefix-free set from the multiset of strings ${s_1, s_2, \ldots, s_k}$. A prefix-free set is a set of distinct strings in which there are no two strings such that one of these strings is a prefix of another one. In particular, an empty set is a valid prefix-free set. For example, if for any $i \neq j$, $s_i$ is not a prefix of $s_j$, then $C (s_1, \ldots, s_k) = 2^{k}$.

Note that we count not the sets themselves, but the ways to construct such sets: the number of ways to choose a subset of indices out of $\{1, 2, \ldots, k\}$ such that the strings with these indices form a prefix-free set. For example, $C($"aa", "aa", "a", "a"$) = 5$: the five ways are to construct an empty set, a set containing the first string, a set containing the second string, a set containing the third string, and a set containing the fourth string.

You are given a string $s$ consisting of $n$ lowercase English letters, and $q$ queries. Let $s[l, r]$ be the substring $s_{l} s_{l + 1} \ldots s_{r - 1} s_r$. For each query denoted as "$k$ $m$ $l_1$ $r_1$ $l_2$ $r_2$ $\ldots$ $l_k$ $r_k$", print one integer: the value $C (s[l_1, r_1], s[l_2, r_2], \ldots, s[l_k, r_k])$, taken modulo $m$.

The first line contains two integers: $n$, the length of $s$, and $q$, the number of queries to answer ($1 \le n \le 4 \cdot 10^{5}$, $1 \le q \le 4 \cdot 10^5$).

The second line contains a string $s$ of length $n$ consisting of lowercase English letters.

Next $q$ lines contain queries, one query per line. Each query has the form "$k$ $m$ $l_1$ $r_1$ $l_2$ $r_2$ $\ldots$ $l_k$ $r_k$" ($1 \le k \le 4 \cdot 10^{5}$, $2 \le m \le 10^{9}$, $1 \le l_j \le r_j \le n$).

The total sum of all $k$ over all queries does not exceed $4 \cdot 10^5$.

For each query, print a line containing a single integer: the value $C (s[l_1, r_1], s[l_2, r_2], \ldots, s[l_k, r_k])$, taken modulo $m$.