Problem Statement

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

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

Input

制約に誤りがあったため、修正しました。$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$ 点が与えられる。

Output

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