题目描述
定义一个正整数的 $\mathrm{highbit}$ 为该数在二进制表示下的最高二进制位的位值，如 $\mathrm{highbit}(22_{(10)})=\mathrm{highbit}(10110_{(2)})=10000_{(2)}=16_{(10)}$。
定义一个正整数的 $\mathrm{lowbit}$ 为该数在二进制表示下的最低非零二进制位的位值，如 $\mathrm{lowbit}(22_{(10)})=\mathrm{lowbit}(10110_{(2)})=10_{(2)}=2_{(10)}$。
再定义两种操作：
- 操作 $1$：将一个正整数 $x$ 变为 $x+\mathrm{lowbit}(x)$。
- 操作 $2$：将一个正整数 $x$ 变为 $x+\mathrm{highbit}(x)$。
现给定一个操作序列和 $q$ 次询问，每次询问包含 $3$ 个正整数 $l,r,x$，表示将 $x$ 从左到右依次执行 $l\sim r$ 的操作，请输出 $x$ 的值，由于答案可能很大，请输出答案对 $10^9+7$ 取模的值。
输入格式
第一行两个正整数 $n,q$。
接下来一行一个字符串 $s$，长度为 $n$，其中仅含有 0，1。
若第 $i$ 个字符为 0，则表示一个 $1$ 操作，即 $x=x+\mathrm{lowbit}(x)$。
若第 $i$ 个字符为 1，则表示一个 $2$ 操作，即 $x=x+\mathrm{highbit}(x)$。
之后 $q$ 行，每行 $3$ 个正整数 $l,r,x$，表示一次询问。
输出格式
对于每一个询问，输出一行一个数表示答案对 $10^9+7$ 取模的结果。
样例
样例输入
8 8
01100001
1 2 3
1 4 9
2 6 9
3 8 9
6 8 2
8 8 3
5 8 6
2 8 17样例输出
8
36
40
64
16
5
64
144数据范围
本题采用捆绑测试。
对于所有测试点，满足 $1\leq n,q\leq 5\times 10^5$，$1\leq x<2^{30}$。详细数据范围如下：
- Subtask #1 (12 pts): $n,q\le 10$，$x\le 32767$。
- Subtask #2 (23 pts): $n,q\le 10^3$。
- Subtask #3 (11 pts): $n,q\leq 10^5$，字符串中仅含有
1。 - Subtask #4 (11 pts): $n,q\leq 10^5$，字符串中仅含有
0。 - Subtask #5 (6 pts): $n,q\leq 10^5$，保证每次询问的 $x$ 均可以表示为 $2^a$ 的形式，$a$ 为非负整数。
- Subtask #6 (15 pts): $n,q\leq 10^5$，保证每次询问的 $x$ 均可以表示为 $2^a+2^b$ 的形式，$a,b$ 均为非负整数。
- Subtask #7 (10 pts): $n,q\le 10^5$。
- Subtask #8 (12 pts): 没有任何附加限制。