You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
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 Format
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 Format
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.

Now solve the problem and return the code.