A12083. Banh-mi

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

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.