Description

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$.

Input Format

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.

Output Format

For each query, output one line with one number, the answer modulo $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

Hint

Constraints

This problem uses bundled testdata.

For all test cases, $1\leq n,q\leq 5\times 10^5$, $1\leq x<2^{30}$. The detailed constraints are as follows:

• 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$, the string contains only 1.
• Subtask #4 (11 pts): $n,q\leq 10^5$, the string contains only 0.
• Subtask #5 (6 pts): $n,q\leq 10^5$, it is guaranteed that in every query, $x$ can be written as $2^a$, where $a$ is a non-negative integer.
• Subtask #6 (15 pts): $n,q\leq 10^5$, it is guaranteed that in every query, $x$ can be written as $2^a+2^b$, where $a,b$ are non-negative integers.
• Subtask #7 (10 pts): $n,q\le 10^5$.
• Subtask #8 (12 pts): No additional constraints.

Translated by ChatGPT 5