Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB
高橋商店では 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
この問題には部分点が設定されている。
Q 行に出力せよ。そのうち i 行目には、i 個目の注文への答えを 1,000,000,007 (10^9+7) で割った余りを出力せよ。
3 5 2 3 2 2 1 3 1 0
3 0
1 つ目の注文は「1 種類目の商品をちょうど 3 個選ばなければならないとき、合計 5 個の商品を選ぶ方法の数を出力せよ」というもので、そのような方法は以下の 3 通りある。
また 2 つ目の注文では 2 種類目と 3 種類目の商品から合計 5 個の商品を選ばなければならないが、商品が足りずそのような方法は存在しないため、0 と出力する。
4 7 5 1 2 3 4 4 0 3 2 2 1 1 1 1 0
0 5 5 9 6