P8055 B Highbit & lowbit

Define the $\mathrm{highbit}$ of a positive integer as the value of its highest binary bit in its binary representation. For example, $\mathrm{highbit}(22_{(10)})=\mathrm{highbit}(10110_{(2)})=10000_{(2)}=16_{(10)}$. Define the $\mathrm{lowbit}$ of a positive integer as the value of its lowest non-zero binary bit in its binary representation. For example, $\mathrm{lowbit}(22_{(10)})=\mathrm{lowbit}(10110_{(2)})=10_{(2)}=2_{(10)}$. Define two operations: - Operation $1$: change a positive integer $x$ into $x+\mathrm{lowbit}(x)$. - Operation $2$: change a positive integer $x$ into $x+\mathrm{highbit}(x)$. Now you are given an operation sequence and $q$ queries. Each query contains $3$ positive integers $l,r,x$, meaning that starting from left to right, apply operations $l \sim r$ to $x$ in order. Output the final value of $x$. Since the answer may be very large, output the result modulo $10^9+7$.

The first line contains two positive integers $n,q$. The next line contains a string $s$ of length $n$, consisting only of `0` and `1`. If the $i$-th character is `0`, it represents an Operation $1$, i.e. $x=x+\mathrm{lowbit}(x)$. If the $i$-th character is `1`, it represents an Operation $2$, i.e. $x=x+\mathrm{highbit}(x)$. Then follow $q$ lines. Each line contains $3$ positive integers $l,r,x$, representing one query.

For each query, output one line with one number, the answer modulo $10^9+7$.

**Constraints** **This problem uses bundled testdata.** For all test cases, $1\leq n,q\leq 5\times 10^5$, $1\leq x