A君とB君はゲームをしています。A君はいくつかの数を選んで袋に入れ、その中からランダムに1つを取り出してB君に当てさせるというゲームをしました。B君はすぐに、期待値（すなわちこれらの数の平均値）を予想するのが最も近いと気づき、毎回期待値を予想するようになりました。A君は退屈し、ゲームを改良しましたが、B君はまたすぐに期待値を予想するのが最善であると気づきました。

何度も改良を重ねた結果、ゲームは次のようになりました。2つの袋からそれぞれランダムに1つずつ数を取り出し、それらを$m$、$n$とします。次に、A君は$m$個のボールと$n$個の袋を用意し、ボールをランダムに袋に入れます。その後、ランダムに1つの袋を選び、B君にその袋の中に何個のボールが入っているかを予想させます（B君は$m$と$n$がそれぞれいくつであるかを知っています）。今、A君は、もしB君が毎回期待値を予想する場合、その「偏差」がどれくらいになるのかに興味を持ちました。A君はあなたに、袋の中の実際のボールの数からB君の予想値を引いた差の$k$乗の期待値を求めるように頼みました。

実際、袋の中の実際のボールの数を$x$とすると、A君が尋ねているものは変数$x$の$k$次中心モーメントと呼ばれ、その定義は $\mathrm{E}\left((x-\mathrm{E}(x))^k\right)$ です。特に、2次中心モーメントは分散です。

入力

入力の1行目には3つの正整数 $N_n$、$N_m$、$N_k$ が含まれており、それぞれ$n$と$m$の袋の数の種類数と、クエリの個数を表します。

続く$N_n$行には、それぞれ2つの正整数 $n_i$ と ${num}_{n_i}$ が含まれており、$n$を取り出す袋の中に$n_i$が${num}_{n_i}$個存在することを表します。

続く$N_m$行には、それぞれ2つの正整数 $m_i$ と ${num}_{m_i}$ が含まれており、$m$を取り出す袋の中に$m_i$が${num}_{m_i}$個存在することを表します。

続く$N_k$行には、それぞれ1つの正整数 $k$ が含まれており、1つのクエリを表します。

出力

答えは必ず有理数になることが証明できます。$N_k$行を出力してください。各行には、1つのクエリに対する答えを$1000000007$（$10^9+7$）で割った余りを出力してください。すなわち、答えを $a/b$ （$a$と$b$は互いに素な正整数）としたとき、出力する整数を$x$とすると、$b \cdot x \equiv a \pmod{1000000007}$ かつ $0 \leq x < 1000000007$ を満たす必要があります。

入出力例

入力 1

1 1 2
3 1
2 1
2
3

出力 1

444444448
481481485

注記 1

$(a, b, c)$ を3つの袋の中のボールの数とします。最初のクエリについて、$(2, 0, 0), (0, 2, 0), (0, 0, 2)$ となる確率はそれぞれ $1/9$ で、分散はそれぞれ $8/9$ です。$(1, 1, 0), (1, 0, 1), (0, 1, 1)$ となる確率はそれぞれ $2/9$ で、分散はそれぞれ $2/9$ です。したがって、分散の期待値は $1/9 \times 8/9 \times 3 + 2/9 \times 2/9 \times 3 = 4/9$ となります。$444444448 \times 9 \equiv 4 \pmod{1000000007}$ です。

入力 2

2 2 2
3 2
2 1
3 2
2 1
2
3

出力 2

172839508
650205766

注記 2

最初のクエリについて、$4/9$ の確率で3袋3ボールとなり、分散の期待値は $2/3$ です。$2/9$ の確率で2袋3ボールとなり、分散の期待値は $3/4$ です。$2/9$ の確率で3袋2ボールとなり、分散の期待値は $4/9$ です。$1/9$ の確率で2袋2ボールとなり、分散の期待値は $1/2$ です。したがって、求める値は $4/9 \times 2/3 + 2/9 \times 3/4 + 2/9 \times 4/9 + 1/9 \times 1/2 = 50/81$ となります。$172839508 \times 81 \equiv 50 \pmod{1000000007}$ です。

制約

すべてのテストデータにおいて、$n_i, m_i \leq 10^9$、$N_n \leq 5000$、$N_m, k, {num}_{n_i}, {num}_{m_i} \leq 2000$、$N_k \leq 200$。