B Highbit & lowbit

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