Given an array $a$ of $N$ integers, support $Q$ queries of the following type:

l r return the number of subsequences between index l to r (inclusive) which have an even sum.

As the results of these queries may be extremely large, output them modulo ${10}^9+7$.

A subsequence can be created from $a$ by deleting some elements (possibly none, but not all). Two subsequences are different if one contains an index from the original array that the other does not have.

Constraints

For all subtasks:

• $1\le N,Q,a_i\le {10}^6$
• $1\le l\le r\le N$

Points Awarded	Additional Constraints
3 points	All $a_i$ are even
5 points	$1\le N,Q\le 3\times {10}^3$
7 points	No further constraints

Input Specification

The first line contains two space-separated integers $N$ and $Q$.

The next line contains $N$ space-separated integers — the array $a$.

The next $Q$ lines each contain two space-separated integers $l_i$, and $r_i$, denoting the $i^{\text{th}}$ query.

Output Specification

Output the answer to each query in order on separate lines.

Sample Input

6 1
4 3 1 2 5 7
2 4

Sample Output

3