D - ぴょんぴょんトレーニング Editorial /

Time Limit: 8 sec / Memory Limit: 256 MB

問題文

跡鼓駄 (あとこだ) 町には ARC 珈琲店があり、競技プログラミング喫茶店として知られている。

高橋君は ARC 珈琲店でアルバイトをしている。

高橋君は ARC 珈琲店に行く際にいつも精進通りという道を通る。精進通りは、高橋君の家と 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