問題文
Atokoda镇有一家ARC咖啡店,号称竞技编程咖啡店。
高桥在 ARC 咖啡店兼职。
高桥去ARC Coffee时,总是经过精进通。精进街连接着高桥家和ARC咖啡厅。
精进街是 这是一条由 N 石头组成的鹅卵石路。这些石头是从高桥家所在的一侧按顺序排列的。 来自 1 它们的编号最大为 N 。
高桥君训练他的腿部和臀部。D 我决定在日美圣神街训练。
i 第一天的训练将进行如下。
- 训练中的石头 如果你在 x ,石头 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 的方法总数。此外, 2 不同的移动方式意味着沿途经过的石子组合也不同。
入力
输入是按以下格式从标准输入给出的。
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 行包含有关训练的信息。这些 D 从行顶部开始 在 i (1 ≦ i ≦ D) 行中, 2 整数 s_i, t_i (1 ≦ s_i < t_i ≦ N) 用空格分隔。这是i 训练当天,石 从 s_i 开始,石头 t_i 表示结束。 满足
部分点
针对此问题设置了部分分数。 如果
- N ≦ 500 的数据集 如果您正确回答 1 ,30 点。
- 没有附加约束的数据集 如果您对 2 的回答正确,除上述之外, 通过 70 点。
出力
D 线输出。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