Pozwólcie, że powiem to wprost: sprawy nie mają się najlepiej. Wieczór, który miał być relaksującym spotkaniem z przyjaciółmi, przybrał fatalny obrót: zostaliście zaatakowani przez chodzącą reklamę taniej wody kolońskiej, a wasz bezcenny argentyński kaktus – jedyna rzecz, która jest dla was ważna – został wyrzucony przez okno.

Zaraz po tym zdarzeniu – a raczej, jak tylko było to fizycznie możliwe – zbiegliście po schodach, aby ocenić straty. I oto był, wasz bezcenny kaktus, żywy! Z kilkoma zadrapaniami tu i ówdzie, ale mimo wszystko żywy. Jak to się stało? Czy wylądował na czymś miękkim? Przepełnieni radością postanawiacie nie szukać odpowiedzi. Czy powiedziałem, że sprawy nie mają się najlepiej? Wykreślcie to, wszystko jest wspaniale – czas na świętowanie! Oczywiście w centrum tej uroczystości znajdzie się wasz zielony, kłujący przyjaciel.

Ci, którzy mniej znają się na botanice, mogą teraz potrzebować przypomnienia: kaktus to spójny graf, w którym każdy wierzchołek leży na co najwyżej jednym cyklu. Aby dodać nastroju, postanawiacie pokolorować każdy wierzchołek swojego kaktusa jednym z $k$ kolorów. Chcecie mieć przy tym dużo swobody, ale chcecie przestrzegać złotej zasady kolorowania kaktusa: żadne dwa sąsiednie wierzchołki nie powinny mieć przypisanego tego samego koloru.

Jedno kolorowanie to za mało, więc postanawiacie, że gdy kolory wyblakną, będziecie kolorować kaktusa ponownie, za każdym razem używając innego kolorowania. Ale jak długo będziecie w stanie to robić? Mając opis kaktusa i liczbę $k$, obliczcie liczbę poprawnych $k$-kolorowań wierzchołków kaktusa. Ponieważ wynik może być bardzo duży, wystarczy, że obliczycie jego resztę z dzielenia przez $10^9 + 7$.

Wejście

Pierwsza linia wejścia zawiera liczbę zestawów danych $z$ ($1 \le z \le 50\,000$). Następnie następują opisy zestawów danych.

Pierwsza linia zestawu danych zawiera trzy liczby całkowite $n$, $m$ oraz $k$ ($1 \le n \le 300\,000$, $0 \le m \le 400\,000$, $2 \le k \le 10^9$) – liczbę wierzchołków i krawędzi kaktusa oraz liczbę kolorów.

Kolejne $m$ linii zawiera po dwie liczby całkowite $u_i, v_i$ ($1 \le u_i \neq v_i \le n$), odpowiadające krawędziom kaktusa. Gwarantuje się, że podany graf jest kaktusem i że każde dwa wierzchołki są połączone co najwyżej jedną krawędzią.

Łączna liczba wierzchołków i krawędzi we wszystkich zestawach danych nie przekracza odpowiednio $3 \cdot 10^6$ oraz $4 \cdot 10^6$.

Wyjście

Dla każdego zestawu danych wypiszcie pojedynczą liczbę całkowitą: liczbę poprawnych kolorowań wierzchołków kaktusa przy użyciu $k$ kolorów, modulo $10^9 + 7$.

Przykład

Wejście 1

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

Wyjście 1

9900
24