C. Banh-mi
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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

Examples
Input
4 2
1011
1 4
3 4
Output
14
3
Input
3 2
111
1 2
3 3
Output
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.