← 返回题目列表

AtCoder · arc027_4

D. Pyon Pyon 训练

中文机器翻译题面 查看原题

問題文

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