Prefix-free Queries

$C (s_1, s_2, \ldots, s_k)$ is the number of ways to build a prefix-free set from the multiset $\{s_1, s_2, \ldots, s_k\}$. A prefix-free set is a set of distinct strings in which no string is a prefix of another. The empty set is a valid prefix-free set. For example, if for every $i \neq j$ the string $s_i$ is not a prefix of $s_j$, then $C (s_1, \ldots, s_k) = 2^{k}$.

We count the ways to build such sets, not the sets themselves. That is, we count the subsets of indices from $\{1, 2, \ldots, k\}$ whose strings form a prefix-free set. For example, $C$("aa", "aa", "a", "a") $= 5$. The five ways are the empty set, and the sets containing only the first, second, third, or fourth string.

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

The first line contains two integers $n$ and $q$ ($1 \le n \le 4 \cdot 10^{5}$, $1 \le q \le 4 \cdot 10^{5}$). The second line contains the string $s$ of length $n$. Each of the next $q$ lines contains one query in the form "$k$ $m$ $l_1$ $r_1$ $\ldots$ $l_k$ $r_k$", where $1 \le k \le 4 \cdot 10^{5}$, $2 \le m \le 10^{9}$, and $1 \le l_j \le r_j \le n$. The sum of all $k$ over all queries does not exceed $4 \cdot 10^{5}$.

For each query, print one line with the value of $C (s[l_1, r_1], \ldots, s[l_k, r_k])$ modulo $m$.