Little A and Little B are playing a game. Little A finds some numbers, puts them into a bag, and then randomly picks one out, asking Little B to guess what it is. Little B quickly discovers that guessing the expectation (i.e., the average of these numbers) is the closest, so he guesses the expectation every time. Little A finds this a bit boring, so he enhances the game, but Little B quickly discovers that guessing the expectation is still the best strategy.

After many enhancements, the game becomes this: randomly pick one number from each of 2 bags, denoted as $m$ and $n$ respectively. Then, Little A takes $m$ balls and $n$ bags, randomly places all the balls into the bags, and then randomly picks one bag, asking Little B to guess how many balls are inside (Little B knows the values of $m$ and $n$). Now, Little A is curious: if Little B always guesses the expectation, what is the "degree of deviation" of the guess? Little A asks you for the expectation of the $k$-th power of the difference between the actual number of balls in the bag and the number Little B guesses.

In fact, if we let $x$ be the actual number of balls in the bag, then what Little A is asking for is called the $k$-th central moment of the variable $x$, defined as $\mathrm{E}\left((x-\mathrm{E}(x))^k\right)$. Specifically, the 2nd central moment is the variance.

Input

The first line of input contains 3 positive integers $N_n$, $N_m$, and $N_k$, representing the number of types of numbers in the bags for $n$ and $m$, and the number of queries, respectively.

The next $N_n$ lines each contain two positive integers $n_i$ and ${num}_{n_i}$, indicating that there are ${num}_{n_i}$ occurrences of $n_i$ in the bag for $n$.

The next $N_m$ lines each contain two positive integers $m_i$ and ${num}_{m_i}$, indicating that there are ${num}_{m_i}$ occurrences of $m_i$ in the bag for $m$.

The next $N_k$ lines each contain a positive integer $k$, representing a query.

Output

It can be proven that the answer is always a rational number. Output $N_k$ lines in total, each containing an integer representing the result of the query modulo $1000000007$ ($10^9+7$). That is, if the answer is $a/b$ (where $a$ and $b$ are coprime positive integers), and you output an integer $x$, you must ensure that $b \cdot x \equiv a \pmod{1000000007}$ and $0\leq x < 1000000007$.

Examples

Input 1

1 1 2
3 1
2 1
2
3

Output 1

444444448
481481485

Note 1

Let $(a,b,c)$ denote the number of balls in the 3 bags. For the first query, the probabilities of $(2,0,0)$, $(0,2,0)$, and $(0,0,2)$ are all $1/9$, and the variance for each is $8/9$. The probabilities of $(1,1,0)$, $(1,0,1)$, and $(0,1,1)$ are all $2/9$, and the variance for each is $2/9$. Thus, the expectation of the variance is $1/9 \times 8/9 \times 3 + 2/9 \times 2/9 \times 3 = 4/9$. $444444448 \times 9 \equiv 4 \pmod{1000000007}$.

Input 2

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

Output 2

172839508
650205766

Note 2

For the first query, there is a $4/9$ probability of having 3 bags and 3 balls, with an expected variance of $2/3$; a $2/9$ probability of 2 bags and 3 balls, with an expected variance of $3/4$; a $2/9$ probability of 3 bags and 2 balls, with an expected variance of $4/9$; and a $1/9$ probability of 2 bags and 2 balls, with an expected variance of $1/2$. Therefore, the required value is $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}$.

Constraints

For all test data, $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$.