Problem Description

A town called Atokoda has a cafe named ARC Cafe, which is known as a competitive programming cafe.

Takahashi works part-time at the ARC Cafe.

Takahashi always takes the path called "Shinjin Street" to go to the ARC Cafe from his home. Shinjin Street connects Takahashi's home and the ARC Cafe.

Shinjin Street is a path made of N stones. The stones are numbered from 1 to N in order from the side where Takahashi's home is located.

Takahashi decided to train on Shinjin Street for D days to strengthen his legs.

On the i-th day of training, it is conducted as follows:

• During the training, if Takahashi is on stone x, he can jump to stones x + 1, x + 2, ..., x + h_x. h_x is constant regardless of the training day.
• At the beginning of the training, Takahashi is on stone s_i.
• The training involves repeatedly jumping from stone s_i to reach stone t_i. Even if he can jump to a stone with a number larger than t_i, he must not move to such a stone.
• The training ends when Takahashi reaches stone t_i.

Takahashi is curious about how many combinations of jumps are possible to move from stone s_i to stone t_i. The number of combinations refers to the total number of different sequences of stones used for jumping. Takahashi intends to verify all combinations by jumping himself.

Aoki, Takahashi's colleague, decided to investigate in advance how many ways there are to jump from stone s_i to stone t_i and inform Takahashi of the results to stop him.

Write a program to determine how many ways there are to jump from stone s_i to stone t_i for each day. Note that two methods of moving are considered different if the sequences of stones passed through are different.

Input Format

The input is given from the standard input in the following format:

$ N $ $ h_1 $ $ h_2 $ ... $ h_N $ $ D $ $ s_1 $ $ t_1 $ $ s_2 $ $ t_2 $ : $ s_D $ $ t_D $

• The first line contains an integer $N\ (2\ ≦\ N\ ≦\ 300,000)$ representing the number of stones.
• The second line contains $ N $ integers separated by spaces. The i-th integer $h_i\ (1\ ≦\ h_i\ ≦\ 10)$ indicates that from stone i, Takahashi can jump to stones i + 1, i + 2, ..., i + h_i. Note that $i + h_i\ ＞\ N$ is possible in this input.
• The third line contains an integer $D\ (1\ ≦\ D\ ≦\ 5,000)$ representing the number of training days.
• The next $ D $ lines contain information about the training. The i-th line contains two integers $s_i,\ t_i\ (1\ ≦\ s_i\ ＜\ t_i\ ≦\ N)$ indicating that on the i-th day, the training starts from stone s_i and ends at stone t_i.

Output Format

Output $ D $ lines. The i-th line should contain the number of combinations of jumps on the i-th day modulo $1000000007\ (=\ 1,000,000,007)$. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

7
1 2 3 2 2 1 1
3
2 6
5 7
1 7

Sample Output #1

6
2
9

Sample Input #2

11
3 1 4 1 5 9 2 6 5 3 5
4
3 7
2 9
1 10
1 11

Sample Output #2

6
22
90
175

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset 1 where $N\ ≦\ 500$ correctly, you will be awarded 30 points.
• If you solve the dataset 2 without additional constraints correctly, you will be awarded an additional 70 points.

Sample Explanation 1

On the first day of training, Takahashi moves from stone 2 to stone 6. In this input, ($ h_2 $, $ h_3 $, $ h_4 $, $ h_5 $, $ h_6 $) =($ 2 $, $ 3 $, $ 2 $, $ 2 $, $ 1 $). The following 6 ways of jumping are possible. 

见题面 Input 部分

见题面 Output 部分