問題文

高橋商店では $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$ 個の商品を選ぶ方法の数を出力せよ」というものであることを表している。

部分点

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

• $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