Banh-mi
Description
JATC loves Banh-mi (a Vietnamese food). His affection for Banh-mi is so much that he always has it for breakfast. This morning, as usual, he buys a Banh-mi and decides to enjoy it in a special way.
First, he splits the Banh-mi into $n$ parts, places them on a row and numbers them from $1$ through $n$. For each part $i$, he defines the deliciousness of the part as $x_i \in \{0, 1\}$. JATC's going to eat those parts one by one. At each step, he chooses arbitrary remaining part and eats it. Suppose that part is the $i$-th part then his enjoyment of the Banh-mi will increase by $x_i$ and the deliciousness of all the remaining parts will also increase by $x_i$. The initial enjoyment of JATC is equal to $0$.
For example, suppose the deliciousness of $3$ parts are $[0, 1, 0]$. If JATC eats the second part then his enjoyment will become $1$ and the deliciousness of remaining parts will become $[1, \_, 1]$. Next, if he eats the first part then his enjoyment will become $2$ and the remaining parts will become $[\_, \_, 2]$. After eating the last part, JATC's enjoyment will become $4$.
However, JATC doesn't want to eat all the parts but to save some for later. He gives you $q$ queries, each of them consisting of two integers $l_i$ and $r_i$. For each query, you have to let him know what is the maximum enjoyment he can get if he eats all the parts with indices in the range $[l_i, r_i]$ in some order.
All the queries are independent of each other. Since the answer to the query could be very large, print it modulo $10^9+7$.
The first line contains two integers $n$ and $q$ ($1 \le n, q \le 100\,000$).
The second line contains a string of $n$ characters, each character is either '0' or '1'. The $i$-th character defines the deliciousness of the $i$-th part.
Each of the following $q$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the segment of the corresponding query.
Print $q$ lines, where $i$-th of them contains a single integer — the answer to the $i$-th query modulo $10^9 + 7$.
Input
The first line contains two integers $n$ and $q$ ($1 \le n, q \le 100\,000$).
The second line contains a string of $n$ characters, each character is either '0' or '1'. The $i$-th character defines the deliciousness of the $i$-th part.
Each of the following $q$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the segment of the corresponding query.
Output
Print $q$ lines, where $i$-th of them contains a single integer — the answer to the $i$-th query modulo $10^9 + 7$.
Samples
4 2
1011
1 4
3 4
14
3
3 2
111
1 2
3 3
3
1
Note
In the first example:
- For query $1$: One of the best ways for JATC to eats those parts is in this order: $1$, $4$, $3$, $2$.
- For query $2$: Both $3$, $4$ and $4$, $3$ ordering give the same answer.
In the second example, any order of eating parts leads to the same answer.