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$ va contine, pe primul rand, $T$, numarul de teste ce se gasesc in fisier.

h2. Restricţii

* $1 ≤ T ≤ 20$

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