AT_arc027_4 [ARC027D] ぴょんぴょんトレーニング

在跡鼓駄（あとこだ）町有一家 ARC 咖啡店，以竞赛编程咖啡馆而闻名。 高桥君在 ARC 咖啡店打工。 高桥君每次去 ARC 咖啡店时，总是会经过一条名为精进通り的道路。精进通り连接着高桥君的家和 ARC 咖啡店。 精进通り是一条由 $N$ 块石头铺成的石板路。这些石头从高桥君家所在的一侧起，依次编号为 $1$ 到 $N$。 为了锻炼身体，高桥君决定在精进通り上训练 $D$ 天。 第 $i$ 天的训练方式如下： - 训练过程中，如果高桥君在第 $x$ 块石头上，他可以跳到第 $x+1$、$x+2$、…、$x+h_x$ 块石头上。$h_x$ 在所有训练日中都是固定的。 - 训练开始时，高桥君在第 $s_i$ 块石头上。 - 训练时，他需要通过不断跳跃，从第 $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$ > $\vdots$ > $s_D\ t_D$ - 第 $1$ 行包含一个整数 $N$，表示石头的数量，$2 \leq N \leq 300,\!000$。 - 第 $2$ 行包含 $N$ 个用空格分隔的整数。第 $i$ 个整数 $h_i$（$1 \leq h_i \leq 10$）表示从第 $i$ 块石头可以跳到第 $i+1$、$i+2$、…、$i+h_i$ 块石头。注意，可能存在 $i+h_i > N$ 的情况。 - 第 $3$ 行包含一个整数 $D$，表示训练天数，$1 \leq D \leq 5,\!000$。 - 接下来的 $D$ 行，每行包含两个用空格分隔的整数 $s_i,\ t_i$（$1 \leq s_i < t_i \leq N$），表示第 $i$ 天的训练从第 $s_i$ 块石头开始，到第 $t_i$ 块石头结束。

输出共 $D$ 行。第 $i$ 行输出第 $i$ 天从 $s_i$ 到 $t_i$ 的跳跃方式数，结果对 $1000000007\ (=1,\!000,\!000,\!007)$ 取模。输出末尾需换行。

## 部分分 本题设有部分分。 - 若能通过 $N \leq 500$ 的数据集 1，可获得 $30$ 分。 - 若能通过无额外限制的数据集 2，可额外获得 $70$ 分。 ## 样例说明 1 第 $1$ 天的训练是从第 $2$ 块石头跳到第 $6$ 块石头。此时输入为 $(h_2, h_3, h_4, h_5, h_6) = (2, 3, 2, 2, 1)$。跳跃方式共有 $6$ 种，如下图所示。 !\[\](/img/arc/027/4-1.png) 由 ChatGPT 4.1 翻译