접두사 없는 질의

$C (s_1, s_2, \ldots, s_k)$는 다중집합 $\{s_1, s_2, \ldots, s_k\}$에서 접두사 없는 집합을 만드는 방법의 수이다. 접두사 없는 집합은 서로 다른 문자열들의 집합이며, 어떤 문자열도 다른 문자열의 접두사가 아니어야 한다. 빈 집합도 유효한 접두사 없는 집합이다. 예를 들어 $i \neq j$인 모든 $i, j$에 대해 $s_i$가 $s_j$의 접두사가 아니라면 $C (s_1, \ldots, s_k) = 2^{k}$이다.

여기서 세는 것은 집합 자체가 아니라 만드는 방법이다. 즉, $\{1, 2, \ldots, k\}$의 добав 인덱스 부분집합 중 해당 인덱스의 문자열들이 접두사 없는 집합을 이루는 경우의 수를 센다. 예를 들어 $C$("aa", "aa", "a", "a") $= 5$이다. 다섯 가지 방법은 빈 집합, 첫 번째 문자열만 담은 집합, 두 번째 문자열만 담은 집합, 세 번째 문자열만 담은 집합, 네 번째 문자열만 담은 집합이다.

길이가 $n$인 영소문자 문자열 $s$와 $q$개의 질의가 주어진다. $s[l, r]$을 부분 문자열 $s_{l} s_{l + 1} \ldots s_{r}$이라 하자. 각 질의 "$k$ $m$ $l_1$ $r_1$ $l_2$ $r_2$ $\ldots$ $l_k$ $r_k$"에 대해 $C (s[l_1, r_1], s[l_2, r_2], \ldots, s[l_k, r_k])$를 $m$으로 나눈 나머지를 출력하라.

첫 번째 줄에 두 정수 $n$과 $q$가 주어진다 ($1 \le n \le 4 \cdot 10^{5}$, $1 \le q \le 4 \cdot 10^{5}$). 두 번째 줄에는 길이 $n$의 문자열 $s$가 주어진다. 이어지는 $q$개의 줄에 각각 "$k$ $m$ $l_1$ $r_1$ $\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$이다. 모든 질의의 $k$를 합하면 $4 \cdot 10^{5}$를 넘지 않는다.

각 질의에 대해 $C (s[l_1, r_1], \ldots, s[l_k, r_k])$를 $m$으로 나눈 나머지를 한 줄에 출력한다.