카투스

솔직히 말하면 상황이 좋지 않다. 친구들과 느긋하게 보내려던 저녁은 싸구려 향수를 온몸에 뿌리고 다니는 걸어 다니는 광고판 같은 사람에게 봉변을 당하면서 엉망이 되었다. 게다가 당신이 유일하게 아끼는 물건인 아르헨티나산 선인장(가격을 매길 수 없는 것)이 창밖으로 던져졌다.

그 직후, 가능한 한 빨리 계단을 뛰어 내려가 피해를 확인했다. 그런데 선인장이 살아 있었다. 몇 군데 긁힌 자국이 있을 뿐이었다. 어떻게 이런 일이 일어났을까? 바닥에 푹신한 무언가가 있었던 걸까? 기쁨이 벅차올라 원인을 따지지 않기로 한다. 상황이 좋지 않다고 했던가? 취소한다. 모든 것이 좋으니 이제 축하할 시간이다. 이 자리의 주인공은 당연히 가시가 따끔한 초록색 친구다.

식물학에 익숙하지 않은 사람을 위해 짚고 넘어가면, 카투스는 각 정점이 많아야 하나의 사이클에 속하는 연결 그래프다. 축제 분위기를 살리기 위해 카투스의 모든 정점을 $k$가지 색 중 하나로 칠하기로 한다. 색을 고를 때 자유를 최대한 누리고 싶지만, 카투스 색칠의 황금률은 지켜야 한다. 인접한 두 정점에는 같은 색을 칠할 수 없다.

한 가지 칠하기로는 부족해 보여서, 색이 바래면 매번 다른 방식으로 카투스를 다시 칠하기로 한다. 그런데 이걸 언제까지 계속할 수 있을까? 카투스의 구조와 수 $k$가 주어졌을 때, 정점을 $k$가지 색으로 올바르게 칠하는 방법의 수를 세어라. 답이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지만 구하면 된다.

첫 줄에 테스트 케이스의 수 $z$($1 \leq z \leq 50000$)가 주어진다. 이후 테스트 케이스가 이어진다.

각 테스트 케이스의 첫 줄에는 세 정수 $n$, $m$, $k$($1 \leq n \leq 300000$, $0 \leq m \leq 400000$, $2 \leq k \leq 10^9$)가 주어진다. 각각 정점의 수, 간선의 수, 색의 수다.

다음 $m$개의 줄에는 각각 두 정수 $u_i$, $v_i$($1 \leq u_i \neq v_i \leq n$)가 주어지며, 이는 카투스의 간선을 나타낸다. 주어진 그래프는 카투스임이 보장되며, 두 정점을 잇는 간선은 최대 하나다.

모든 테스트 케이스의 정점 수 합은 $3 \cdot 10^6$을, 간선 수 합은 $4 \cdot 10^6$을 넘지 않는다.

각 테스트 케이스마다 카투스의 정점을 $k$가지 색으로 올바르게 칠하는 방법의 수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.