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 500000$
$1\le l\le r\le |S|$
$0\le M\le 500000$

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