Description

给定一个长度为 $n$ 的 01 串 $s$，$q$ 次询问：

• 给定 $l,r,k$，问 $s[l,r]$ 中选两个长度为 $k$ 的子序列的 xor 最大是多少，01 串看成 $2$ 进制后转成 $10$ 进制。两个子序列要满足：设第一个子序列下标是 $p_1,p_2,\cdots ,p_k$，其中 $l\le p_i\le r$；设第二个子序列下标是 $q_1,q_2,\cdots ,q_k$，其中 $l\le q_i\le r$，则对于任意 $1\le i,j\le k$，$p_i\neq q_j$。

最大指的是「01 串看成 $2$ 进制后转成 $10$ 进制」数值最大。

比如，如果我们 $0101010111$ 中选择了 $01\bold{0}1\bold{0}101\bold{1}\bold{1}$（前两个是第一个序列，后两个是第二个序列），答案是 $(00)_2\oplus (11)_2=(3)_{10}$。

由于答案可能过大，所以请输出答案对 $10^9+7$ 取模后的结果。

Input Format

第一行输入正整数 $n,q$。

第二行输入字符串 $s$。

第 $3\sim q+2$ 行，输入询问中的 $l,r,k$。

Output Format

输出 $q$ 行，表示答案。

10 5
0101001111
1 10 5
1 4 2
4 10 3
1 6 3
7 10 2

30
3
6
6
0

Hint

对于 $100\%$ 的数据，$1\le n,q\le 10^6$，$2\le 2k\le r-l+1$，$s$ 由 $\tt0,\tt1$ 构成。

特殊性质 A：$s$ 中 $1$ 的个数 $\le 10$ 且 $k \ge 10$。