== include(page="template/taskheader" task_id="arugaktus") ==

Poveste şi cerinţă...
 

Arugak este foarte interesata de grafuri, deci a definit un nou tip de graf: arugaktusul. Un arugaktus este un graf nedirectionat conex unde oricare ciclu simplu are lungime impara.
Arugak a desenat un arugaktus cu $N$ noduri si $M$ muchii. De asemenea vrea sa cumpere $K$ creioane colorate diferite, dar nu este sigura cat ar trebui sa fie $K$. Pentru a decide, ea are $Q$ valori posibile pentru $K$, si vrea sa stie, pentru fiecare valoare, in cate moduri poate colora nodurile arugaktusului cu $K$ culori astfel incat oricare doua noduri legate printr-o muchie sunt colorate diferit, modulo $1.000.000.7$. O puteti ajuta ?
 

h2. Date de intrare

Fişierul de intrare $arugaktus.in$ ...

Fişierul de intrare $arugaktus.in$ va contine, pe primul rand, $T$, numarul de teste ce se gasesc in fisier.
Prima linie a oricarui test va contine numerele $N, M, Q$, cu semnificatia de mai sus.
Urmatoarele $M$ linii contin o pereche $i, j$ de noduri, care reprezinta ca exista o muchie intre nodul $i$ si nodul $j$.
Urmatoarele $Q$ linii vor contine cate o valoare diferita a lui $K$ de care e Arugak interesata.

h2. Date de ieşire

În fişierul de ieşire $arugaktus.out$ ...

În fişierul de ieşire $arugaktus.out$ se vor gasi raspunsurile pentru cele $T$ teste, in ordine.
Pentru fiecare test, afisati, pe cate un rand, raspunsul pentru fiecare valoare a lui $K$ de care este Arugak intersata, in ordine.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100.000$
* $1 ≤ Q ≤ 10$
* $1 ≤ K ≤ 1.000.000.000$

h2. Exemplu
table(example). |_. arugaktus.in |_. arugaktus.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|1
5 5 3
1 2
2 3
3 1
1 4
1 5
1
2
3
 
|0
0
24

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="arugaktus") ==