题目描述

定义一个正整数的 $\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): 没有任何附加限制。