Mały A i mały B grają w grę. Mały A znajduje kilka liczb, wkłada je do worka, a następnie losowo wyciąga jedną z nich i prosi małego B o odgadnięcie, jaka to liczba. Mały B szybko odkrywa, że zgadywanie wartości oczekiwanej (czyli średniej arytmetycznej tych liczb) jest najbardziej opłacalne, więc za każdym razem typuje wartość oczekiwaną. Mały A uznaje to za nudne, więc urozmaica grę, ale mały B szybko orientuje się, że strategia zgadywania wartości oczekiwanej nadal jest najlepsza.

Po wielu urozmaiceniach gra wygląda teraz tak: z dwóch worków losowo wyciąga się po jednej liczbie, oznaczając je odpowiednio jako $m$ oraz $n$. Następnie mały A bierze $m$ kul i $n$ worków, umieszcza kule losowo w workach, po czym losowo wybiera jeden worek i prosi małego B o odgadnięcie, ile jest w nim kul (mały B wie, ile wynoszą $m$ oraz $n$). Teraz mały A jest ciekaw, jaki jest „stopień odchylenia” zgadywania, jeśli mały B zawsze typuje wartość oczekiwaną. Mały A pyta o wartość oczekiwaną $k$-tej potęgi różnicy między rzeczywistą liczbą kul w worku a liczbą wytypowaną przez małego B.

W rzeczywistości, jeśli przyjmiemy, że rzeczywista liczba kul w worku to zmienna losowa $x$, to pytanie małego A dotyczy $k$-tego momentu centralnego zmiennej $x$, którego definicja to $\mathrm{E}\left((x-\mathrm{E}(x))^k\right)$. W szczególności, drugi moment centralny to wariancja.

Wejście

Pierwsza linia wejścia zawiera $3$ liczby całkowite dodatnie $N_n$, $N_m$ oraz $N_k$, oznaczające odpowiednio liczbę rodzajów liczb w workach dla $n$ i $m$ oraz liczbę zapytań.

Następnie $N_n$ linii, z których każda zawiera dwie liczby całkowite dodatnie $n_i$ oraz ${num}_{n_i}$, co oznacza, że w worku z liczbami $n$ znajduje się ${num}_{n_i}$ wystąpień liczby $n_i$.

Następnie $N_m$ linii, z których każda zawiera dwie liczby całkowite dodatnie $m_i$ oraz ${num}_{m_i}$, co oznacza, że w worku z liczbami $m$ znajduje się ${num}_{m_i}$ wystąpień liczby $m_i$.

Następnie $N_k$ linii, z których każda zawiera jedną liczbę całkowitą dodatnią $k$, oznaczającą pojedyncze zapytanie.

Wyjście

Można udowodnić, że odpowiedź jest zawsze liczbą wymierną. Należy wypisać $N_k$ linii, z których każda zawiera liczbę całkowitą będącą wynikiem zapytania modulo $1000000007$ ($10^9+7$). Oznacza to, że jeśli odpowiedzią jest $a/b$ (gdzie $a$ i $b$ są względnie pierwszymi liczbami całkowitymi dodatnimi), należy wypisać taką liczbę całkowitą $x$, dla której $b \cdot x \equiv a \pmod{1000000007}$ oraz $0\leq x < 1000000007$.

Przykład

Przykład 1

Wejście 1

1 1 2
3 1
2 1
2
3

Wyjście 1

444444448
481481485

Uwagi 1

Niech $(a,b,c)$ oznacza liczbę kul w $3$ workach. Dla pierwszego zapytania prawdopodobieństwo wystąpienia $(2,0,0)$, $(0,2,0)$, $(0,0,2)$ wynosi $1/9$ dla każdego, a wariancja wynosi $8/9$. Prawdopodobieństwo wystąpienia $(1,1,0)$, $(1,0,1)$, $(0,1,1)$ wynosi $2/9$ dla każdego, a wariancja wynosi $2/9$. Zatem wartość oczekiwana wariancji wynosi $1/9 \cdot 8/9 \cdot 3 + 2/9 \cdot 2/9 \cdot 3 = 4/9$. Liczba $444444448 \cdot 9$ jest przystająca do $4$ modulo $1000000007$.

Przykład 2

Wejście 2

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

Wyjście 2

172839508
650205766

Uwagi 2

Dla pierwszego zapytania, z prawdopodobieństwem $4/9$ mamy $3$ worki i $3$ kule, wartość oczekiwana wariancji wynosi $2/3$; z prawdopodobieństwem $2/9$ mamy $2$ worki i $3$ kule, wartość oczekiwana wariancji wynosi $3/4$; z prawdopodobieństwem $2/9$ mamy $3$ worki i $2$ kule, wartość oczekiwana wariancji wynosi $4/9$; z prawdopodobieństwem $1/9$ mamy $2$ worki i $2$ kule, wartość oczekiwana wariancji wynosi $1/2$. Zatem szukana wartość wynosi $4/9 \times 2/3 + 2/9 \times 3/4 + 2/9 \times 4/9 + 1/9 \times 1/2 = 50/81$. Liczba $172839508 \cdot 81$ jest przystająca do $50$ modulo $1000000007$.

Ograniczenia

Dla wszystkich danych testowych: $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$.