Gokku and Tiwari have a test tomorrow. Tiwari found out that problemset has n questions and score of problems are stored in a array X, every question has $score \le 10$. A test can't have $total score \gt 100$ so only a subarray of the array X would be taken as the question of the test.

Tiwari also found a list which has q pair of integers l and r each pair suggested a subarray from $l^{th}$ element of array to $r^{th}$ element of array which could be given as question in the test .

Now, Tiwari wants to know in how many ways he can get more marks than Gokku for the given l and r.

As the number can be large, you need to output the number of ways % $1000000007$.

Note:- Please read the sample explanation for better understanding.

Input

First line contain a single integer n as specified in problem statement.

Second line contains n space separated integers elements of array X

Third line contains a single integer q as specified in problem statement

Next q lines contain a pair of space separated integers l and r

Output

Print number of ways in which Tiwari gets more marks than Gokku for each query in new line.

Constraints

$1 \le n\le 1000000$

$1 \le l,r \le 1000000$

$X[l]+X[l+1]+......+X[r] \le 100$

$q \le 200$