А и Б играют в игру. А выбирает несколько чисел, кладёт их в мешок, а затем случайным образом достаёт одно из них и просит Б угадать, какое именно. Б быстро понял, что лучше всего угадывать математическое ожидание (среднее арифметическое этих чисел), поэтому каждый раз называет его. А стало скучно, и он усложнил игру, но Б снова быстро понял, что стратегия с математическим ожиданием оптимальна.

После множества усложнений игра стала выглядеть так: из двух мешков случайным образом достаётся по одному числу, которые обозначаются как $m$ и $n$ соответственно. Затем А берёт $m$ шаров и $n$ мешков, случайным образом распределяет шары по мешкам, после чего случайным образом выбирает один из мешков и просит Б угадать, сколько в нём шаров (Б знает значения $m$ и $n$). Теперь А стало любопытно: если Б всегда называет математическое ожидание, какова будет «степень отклонения» его догадки? А просит вас найти математическое ожидание $k$-й степени разности между фактическим количеством шаров в мешке и числом, которое назвал Б.

На самом деле, если обозначить фактическое количество шаров в мешке как $x$, то то, о чём спрашивает А, называется $k$-м центральным моментом случайной величины $x$, который определяется как $\mathrm{E}\left((x-\mathrm{E}(x))^k\right)$. В частности, 2-й центральный момент — это дисперсия.

Входные данные

Первая строка содержит 3 целых положительных числа $N_n$, $N_m$ и $N_k$, обозначающие количество видов чисел в мешках для $n$ и $m$, а также количество запросов соответственно.

Далее следуют $N_n$ строк, каждая из которых содержит два целых положительных числа $n_i$ и ${num}_{n_i}$, означающих, что в мешке для $n$ находится ${num}_{n_i}$ чисел, равных $n_i$.

Далее следуют $N_m$ строк, каждая из которых содержит два целых положительных числа $m_i$ и ${num}_{m_i}$, означающих, что в мешке для $m$ находится ${num}_{m_i}$ чисел, равных $m_i$.

Далее следуют $N_k$ строк, каждая из которых содержит одно целое положительное число $k$, обозначающее запрос.

Выходные данные

Можно доказать, что ответ всегда является рациональным числом. Выведите $N_k$ строк, по одному целому числу в каждой, представляющему ответ на запрос по модулю $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 \cdot 8/9 \cdot 3 + 2/9 \cdot 2/9 \cdot 3 = 4/9$. Число $444444448 \cdot 9$ сравнимо с $4$ по модулю $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$ сравнимо с $50$ по модулю $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$.