令 $C(s_1, s_2, \dots, s_k)$ 为从多重集字符串 $s_1, s_2, \dots, s_k$ 中构造前缀无关集的方法数。前缀无关集是指一组不同的字符串，其中不存在两个字符串使得其中一个是另一个的前缀。特别地，空集是一个有效的前缀无关集。例如，如果对于任意 $i \neq j$，$s_i$ 都不是 $s_j$ 的前缀，则 $C(s_1, \dots, s_k) = 2^k$。

注意，我们计算的不是集合本身，而是构造这些集合的方法：即选择 $\{1, 2, \dots, k\}$ 的一个子集，使得这些下标对应的字符串构成一个前缀无关集的方法数。例如，$C(\text{"aa"}, \text{"aa"}, \text{"a"}, \text{"a"}) = 5$：这五种方法分别是构造空集、包含第一个字符串的集合、包含第二个字符串的集合、包含第三个字符串的集合以及包含第四个字符串的集合。

给定一个由 $n$ 个小写英文字母组成的字符串 $s$ 以及 $q$ 次查询。令 $s[l, r]$ 为子串 $s_l s_{l+1} \dots s_r$。对于每个查询，格式为 “$k \ m \ l_1 \ r_1 \ l_2 \ r_2 \dots l_k \ r_k$”，输出一个整数：$C(s[l_1, r_1], s[l_2, r_2], \dots, s[l_k, r_k])$ 对 $m$ 取模的结果。

输入格式

第一行包含两个整数：$n$（字符串 $s$ 的长度）和 $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 \ l_2 \ r_2 \dots 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], s[l_2, r_2], \dots, s[l_k, r_k])$ 对 $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