AT_arc028_4 [ARC028D] 注文の多い高橋商店

[problemUrl]: https://atcoder.jp/contests/arc028/tasks/arc028_4 高橋商店では $ N $ 種類の商品が売られています。「どの種類の商品がいくつあるか」の情報が与えられるので、「合計 $ M $ 個の商品を選ぶ方法」の数を求めて下さい。ただし、同じ種類の商品は区別しないこととします。 いや、これは少し簡単過ぎるので、ちょっとした注文も追加しよう。整数 $ k $, $ x $ からなる $ Q $ 個の注文を用意したので、それぞれについて「$ k_i $ 種類目の商品をちょうど $ x_i $ 個選ばなければならないとき、合計 $ M $ 個の商品を選ぶ方法」の数を求めて下さい。

制約に誤りがあったため、修正しました。$ 1\ ≦\ Q\ ≦\ 100,000 $→$ 1\ ≦\ Q\ ≦\ 500,000 $（22:15） 入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ Q $ $ a_1 $ $ a_2 $ … $ a_N $ $ k_1 $ $ x_1 $ $ k_2 $ $ x_2 $ : $ k_Q $ $ x_Q $ - $ 1 $ 行目には、商品の種類数を表した整数 $ N\ (1\ ≦\ N\ ≦\ 2000) $ と、選ぶ商品の個数を表す整数 $ M\ (1\ ≦\ M\ ≦\ 2000) $ と、注文の個数を表した整数 $ Q\ (1\ ≦\ Q\ ≦\ 500,000) $ が空白区切りで与えられる。 - $ 2 $ 行目では、各種類の商品の個数の情報がスペース区切りで $ N $ 個与えられる。このうち $ i $ 番目では、$ i $ 種類目の商品の個数を表す整数 $ a_i\ (1\ ≦\ a_i\ ≦\ M) $ が与えられる。 - $ 3 $ 行目からの $ Q $ 行では、注文に関する情報が与えられる。このうち $ i $ 行目では、$ 2 $ つの整数 $ k_i\ (1\ ≦\ k_i\ ≦\ N) $, $ x_i\ (1\ ≦\ x_i\ ≦\ a_{k_i}) $ が空白区切りで与えられる。これは、$ i $ 個目の注文が「$ k_i $ 種類目の商品をちょうど $ x_i $ 個選ばなければならないとき、合計 $ M $ 個の商品を選ぶ方法の数を出力せよ」というものであることを表している。

$ Q $ 行に出力せよ。そのうち $ i $ 行目には、$ i $ 個目の注文への答えを $ 1,000,000,007\ (10^9+7) $ で割った余りを出力せよ。

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 100,\ M\ ≦\ 100,\ Q\ ≦\ 100 $ を満たすテストケースすべてに正解した場合は $ 10 $ 点が与えられる。 - $ N\ ≦\ 100,\ M\ ≦\ 100 $ を満たすテストケースすべてに正解した場合はさらに $ 20 $ 点が与えられる。 - $ Q\ ≦\ 1000 $ を満たすテストケースすべてに正解した場合はさらに $ 50 $ 点が与えられる。 ### Sample Explanation 1 $ 1 $ つ目の注文は「$ 1 $ 種類目の商品をちょうど $ 3 $ 個選ばなければならないとき、合計 $ 5 $ 個の商品を選ぶ方法の数を出力せよ」というもので、そのような方法は以下の $ 3 $ 通りある。 - $ 1 $ 種類目の商品を $ 3 $ 個、$ 2 $ 種類目の商品を $ 2 $ 個、$ 3 $ 種類目の商品を $ 0 $ 個選ぶ。 - $ 1 $ 種類目の商品を $ 3 $ 個、$ 2 $ 種類目の商品を $ 1 $ 個、$ 3 $ 種類目の商品を $ 1 $ 個選ぶ。 - $ 1 $ 種類目の商品を $ 3 $ 個、$ 2 $ 種類目の商品を $ 0 $ 個、$ 3 $ 種類目の商品を $ 2 $ 個選ぶ。 また $ 2 $ つ目の注文では $ 2 $ 種類目と $ 3 $ 種類目の商品から合計 $ 5 $ 個の商品を選ばなければならないが、商品が足りずそのような方法は存在しないため、$ 0 $ と出力する。