Serena is learning about binary numbers in math class! She is given a binary number ~S~, and she is also given series of ~M~ operations which she must perform on it. In one operation, she sets all bits in the 1-indexed range ~[l,r]~ to ~1~, and outputs the base-10 value of the binary number, modulo ~10^9+7~.

The base-10 value of a binary number ~S~ of length ~n~ consisting of digits ~0~ and ~1~ is given by the sum of ~S_i \times 2^{n-i}~ over all ~i~ in ~[1, n]~.

Input Specification

The first line contains two space-separated integers, ~|S|~ and ~M~, the length of the number and the number of operations.
The next line contains ~S~, the original binary number.
The next ~M~ lines contain two space-separated integers, ~l~ and ~r~, representing an operation described in the problem statement.

Output Specification

For each operation, output the base-10 value of the binary number after performing the operation, modulo ~10^9+7~.

Constraints

In all subtasks,
~1 \le |S| \le 500\,000~
~1 \le l \le r \le |S|~
~0 \le M \le 500\,000~

Subtask 1 [20%]

~1 \le |S| \le 20~

Subtask 2 [80%]

No additional constraints.

Sample Input 1

5 2
01000
1 3
2 4

Sample Output 1

28
30