Soyons francs : les choses ne se passent pas très bien. Ce qui devait être une soirée relaxante entre amis a pris une tournure désastreuse : vous avez été agressé par une publicité vivante pour de l'eau de Cologne bon marché, et votre inestimable cactus argentin — la seule chose à laquelle vous tenez — a été jeté par la fenêtre.

Juste après l'incident — ou, devrais-je dire, dès que cela a été physiquement possible — vous avez dévalé les escaliers pour évaluer les dégâts. Et là, il était, votre précieux cactus, vivant ! Avec quelques égratignures ici et là, mais vivant tout de même. Comment cela a-t-il pu arriver ? A-t-il atterri sur quelque chose de mou ? Submergé par la joie, vous décidez de ne pas chercher de réponses. Ai-je dit que les choses ne se passaient pas bien ? Oubliez cela, tout va pour le mieux — et il est temps de faire la fête ! Bien sûr, au cœur de cette célébration se trouvera votre ami vert et piquant.

Ceux qui sont moins familiers avec la botanique apprécieront peut-être un rappel : un cactus est un graphe connexe où chaque sommet appartient au plus à un cycle. Pour ajouter à l'ambiance festive, vous décidez de colorier chaque sommet de votre cactus avec l'une des $k$ couleurs. Vous aimeriez vous donner beaucoup de liberté ici, mais vous voulez respecter la règle d'or du coloriage de cactus : deux sommets adjacents ne doivent pas se voir attribuer la même couleur.

Un coloriage ne semble pas suffisant, alors vous décidez qu'une fois les couleurs fanées, vous recolorerez le cactus encore et encore, en utilisant un coloriage différent à chaque fois. Mais combien de temps pourrez-vous continuer ainsi ? Étant donné la description de votre cactus et le nombre $k$, comptez le nombre de coloriages corrects des sommets du cactus avec $k$ couleurs. Comme la réponse peut être très grande, il suffit de calculer son reste modulo $10^9 + 7$.

Entrée

La première ligne de l'entrée contient le nombre de cas de test $z$ ($1 \le z \le 50\,000$). Les descriptions des cas de test suivent.

La première ligne d'un cas de test contient trois entiers $n$, $m$ et $k$ ($1 \le n \le 300\,000$, $0 \le m \le 400\,000$, $2 \le k \le 10^9$) — le nombre de sommets et d'arêtes de votre cactus, et le nombre de couleurs.

Les $m$ lignes suivantes contiennent chacune deux entiers $u_i$, $v_i$ ($1 \le u_i \neq v_i \le n$), correspondant aux arêtes du cactus. Il est garanti que le graphe donné est un cactus et que deux sommets quelconques sont reliés par au plus une arête.

Le nombre total de sommets et d'arêtes dans tous les cas de test ne dépasse pas respectivement $3 \cdot 10^6$ et $4 \cdot 10^6$.

Sortie

Pour chaque cas de test, affichez un seul entier : le nombre de coloriages propres des sommets du cactus avec $k$ couleurs, modulo $10^9 + 7$.

Exemples

Entrée 1

2
2 1 100
1 2
6 7 3
1 2
2 3
3 1
4 5
5 6
6 4
1 4

Sortie 1

9900
24