시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 1 1 1 100.000%

문제

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$.

예제 입력 1

10 6
aabbaacaba
4 30 1 2 5 6 10 10 10 10
5 20 1 2 3 4 5 6 7 8 9 10
1 2 1 10
3 20 9 9 7 7 8 8
5 20 6 6 7 7 8 8 9 9 10 10
4 20 1 1 2 2 3 3 4 4

예제 출력 1

5
4
0
8
16
9