AtCoder Regular Contest 028

D - 注文の多い高橋商店


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

高橋商店では N 種類の商品が売られています。「どの種類の商品がいくつあるか」の情報が与えられるので、「合計 M 個の商品を選ぶ方法」の数を求めて下さい。ただし、同じ種類の商品は区別しないこととします。

いや、これは少し簡単過ぎるので、ちょっとした注文も追加しよう。整数 k, x からなる Q 個の注文を用意したので、それぞれについて「k_i 種類目の商品をちょうど x_i 個選ばなければならないとき、合計 M 個の商品を選ぶ方法」の数を求めて下さい。


入力

制約に誤りがあったため、修正しました。1 ≦ Q ≦ 100,0001 ≦ Q ≦ 500,000(22:15)

入力は以下の形式で標準入力から与えられる。

N M Q
a_1 a_2a_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 個の商品を選ぶ方法の数を出力せよ」というものであることを表している。

部分点

この問題には部分点が設定されている。

  • N ≦ 100, M ≦ 100, Q ≦ 100 を満たすテストケースすべてに正解した場合は 10 点が与えられる。
  • N ≦ 100, M ≦ 100 を満たすテストケースすべてに正解した場合はさらに 20 点が与えられる。
  • Q ≦ 1000 を満たすテストケースすべてに正解した場合はさらに 50 点が与えられる。

出力

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


入力例1

3 5 2
3 2 2
1 3
1 0

出力例1

3
0

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 と出力する。


入力例2

4 7 5
1 2 3 4
4 0
3 2
2 1
1 1
1 0

出力例2

0
5
5
9
6

Submit提出する