问题

在跡鼓駄（あとこだ）町中有一家名为 ARC 的咖啡店，被称为竞技编程咖啡店。

高桥君在 ARC 咖啡店打工。

高桥君每次去 ARC 咖啡店都会经过一条名为精進通り的街道。精進通り是由 $N$ 块石头构成的石板路。石头从高桥君家一侧开始，依次编号为 $1$ 到 $N$。

为了锻炼腿部力量，高桥君决定在精進通り上进行连续 $D$ 天的训练。

第 $i$ 天的训练如下：

• 在训练过程中，如果站在石头 $x$ 上，可以从石头 $x$ 跳到 $x + 1$, $x + 2$, … , $x + h_x$。其中 $h_x$ 是固定不变的。
• 训练开始时，站在石头 $s_i$ 上。
• 训练时，要通过连续跳跃来到达石头 $t_i$。即使中途也能跳到比 $t_i$ 更大的石头，但不能跳到比 $t_i$ 更大的石头上。
• 当达到石头 $t_i$ 后，训练结束。

高桥君想知道从石头 $s_i$ 跳到石头 $t_i$ 有多少种跳跃方式。跳跃方式指的是在跳跃时所使用的石头组合的总数。高桥君打算亲自尝试所有的组合。

同事青木君决定在高桥君开始训练之前，提前调查从石头 $s_i$ 跳到石头 $t_i$ 有多少种跳跃方式，并将结果告诉高桥君。

请编写一个程序，对于每一天，计算从石头 $s_i$ 跳到石头 $t_i$ 一共有多少种跳跃方式。注意，两种不同的跳跃方式指的是经过的石头组合不同。

---

输入

从标准输入中按以下格式给出输入。

$N$

$h_1$ $h_2$ ... $h_N$

$D$

$s_1$ $t_1$

$s_2$ $t_2$

:

$s_D$ $t_D$

• 第 $1$ 行为一个整数 $N (2 ≦ N ≦ 300,000)$，表示石头的数量。
• 第 $2$ 行为由空格分隔的 $N$ 个整数。这些整数中的第 $i (1 ≦ i ≦ N)$ 个整数 $h_i (1 ≦ h_i ≦ 10)$ 表示从石头 $i$ 跳跃可以到达石头 $i + 1$, $i + 2$, … , $i + h_i$。请注意，输入中也包含 $i + h_i ＞ N$ 的情况。
• 第 $3$ 行为一个整数 $D (1 ≦ D ≦ 5,000)$，表示训练的天数。
• 第 $4$ 行到第 $D$ 行为关于训练的信息。其中第 $i (1 ≦ i ≦ D)$ 行有两个整数 $s_i, t_i (1 ≦ s_i ＜ t_i ≦ N)$，表示第 $i$ 天的训练从石头 $s_i$ 开始，以石头 $t_i$ 结束。

---

部分分

本问题设置了部分分。

• 对于满足 $N ≦ 500$ 的数据集 $1$ 给出正确答案，将获得 $30$ 分。
• 对于没有额外限制的数据集 $2$ 给出正确答案，除了以上分数外还将获得 $70$ 分。

---

输出

请输出 $D$ 行。第 $i$ 行输出第 $i$ 天跳跃的方式总数模 $1000000007 (= 1,000,000,007)$ 的余数。输出应以换行符结尾。

---

示例1

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

输出示例1

6
2
9

在第 $1$ 天的训练中，要从石头 $2$ 跳到石头 $6$。在这个示例中，($h_2$, $h_3$, $h_4$, $h_5$, $h_6$) =($2$, $3$, $2$, $2$, $1$)。可以找到以下 $6$ 种跳跃方式。

---

示例2

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

输出示例2

6
22
90
175