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

[problemUrl]: https://atcoder.jp/contests/arc027/tasks/arc027_4 跡鼓駄 (あとこだ) 町には 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 $ で終了することを表す。

$ D $ 行にわたって出力せよ。$ D $ 行のうち $ i $ 行目には、$ i $ 日目におけるジャンプで移動する組み合わせ数を $ 1000000007\ (=\ 1,000,000,007) $ で割った余りを出力せよ。出力の末尾にも改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 500 $ を満たすデータセット $ 1 $ に正解した場合は、$ 30 $ 点が与えられる。 - 追加制約のないデータセット $ 2 $ に正解した場合は、上記とは別に $ 70 $ 点が与えられる。 ### Sample Explanation 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)