P8055 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$ 取模的结果。

**【数据范围】** **本题采用捆绑测试。** 对于所有测试点，满足 $1\leq n,q\leq 5\times 10^5$，$1\leq x