26827번 - Przedszkole 다국어

문제

Codziennie rano w przedszkolu pani przedszkolanka rozdaje dzieciom zabawki. Żeby nie było bałaganu, każdemu z n dzieci daje dokładnie jedną zabawkę. Czasem dzieci bawią się same, ale czasem niektóre z nich bawią się parami (ale tylko wtedy, gdy się lubią).

Pani przedszkolanka ma k rodzajów zabawek. Zastanawia się, na ile różnych sposobów może rozdać zabawki dzieciom, przy czym jeśli dwoje dzieci się lubi, to powinny dostać inne rodzaje zabawek (żeby miały dwie różne zabawki, gdy postanowią bawić się razem).

입력

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite n, m oraz z (1 ≤ n ≤ 100 000, 0 ≤ m ≤ min(100 000, n(n − 1)/2), 1 ≤ z ≤ 1000), pooddzielane pojedynczymi odstępami i określające kolejno: liczbę dzieci w przedszkolu, liczbę par dzieci, które się lubią, oraz liczbę zapytań.

W kolejnych m wierszach znajdują się opisy kolejnych par dzieci, które się lubią: opis składa się z dwóch liczb naturalnych a_i oraz b_i określających numery dzieci, które się lubią. Dla uproszczenia dzieci numerowane są kolejnymi liczbami od 1 do n. Pary podane na wejściu nie powtarzają się.

W kolejnych z wierszach znajdują się zapytania: i-ty z tych wierszy zawiera liczbę k_i (1 ≤ k_i ≤ 10⁹).

출력

Na wyjście należy wypisać dokładnie z wierszy: i-ty z nich ma zawierać liczbę sposobów, na które można rozdać dzieciom zabawki, jeśli dostępne jest ich k_i rodzajów. Wyniki należy wypisać modulo 10⁹ + 7 (tzn. należy wypisać resztę z dzielenia wyniku przez 10⁹ + 7).

제한

힌트