솔직히 말해서, 상황이 좋지 않습니다. 친구들과 편안한 저녁을 보내려던 계획은 엉망이 되었습니다. 저렴한 향수를 뿌린 광고판 같은 사람에게 습격을 당했고, 당신이 가장 아끼는 소중한 아르헨티나 선인장이 창밖으로 던져졌기 때문입니다.

사건 직후, 아니 정확히는 물리적으로 가능한 가장 빨리, 당신은 계단을 뛰어 내려가 피해 상황을 확인했습니다. 그런데 거기, 당신의 소중한 선인장이 살아있었습니다! 여기저기 긁힌 자국은 있었지만, 어쨌든 살아있었습니다. 어떻게 이런 일이 일어났을까요? 푹신한 곳에 떨어졌을까요? 기쁨에 압도된 당신은 이유를 묻지 않기로 했습니다. 상황이 좋지 않다고 말했나요? 취소합니다. 모든 것이 완벽합니다. 이제 축하할 시간입니다! 물론, 이 축하의 중심에는 당신의 초록색 가시 친구가 있을 것입니다.

식물학에 익숙하지 않은 분들을 위해 다시 설명하자면, 선인장(cactus)은 각 정점이 최대 하나의 사이클에 포함되는 연결 그래프입니다. 축제 분위기를 더하기 위해, 당신은 선인장의 모든 정점을 $k$개의 색상 중 하나로 칠하기로 했습니다. 여기서 많은 자유를 누리고 싶지만, 선인장 색칠의 황금률은 지키고 싶습니다. 바로 인접한 두 정점은 같은 색을 가져서는 안 된다는 것입니다.

한 가지 색칠만으로는 부족하다고 생각한 당신은 색이 바랠 때마다 매번 다른 색칠 방법을 사용하여 선인장을 계속해서 다시 칠하기로 했습니다. 하지만 얼마나 오랫동안 이 일을 계속할 수 있을까요? 선인장에 대한 설명과 색상의 수 $k$가 주어질 때, 선인장의 정점을 $k$개의 색으로 올바르게 칠하는 방법의 수를 구하세요. 답이 매우 클 수 있으므로, $10^9 + 7$로 나눈 나머지를 구하면 충분합니다.

입력

첫 번째 줄에는 테스트 케이스의 수 $z$ ($1 \le z \le 50\,000$)가 주어집니다. 각 테스트 케이스에 대한 설명이 이어집니다.

각 테스트 케이스의 첫 번째 줄에는 세 정수 $n, m, k$ ($1 \le n \le 300\,000$, $0 \le m \le 400\,000$, $2 \le k \le 10^9$)가 주어지며, 이는 각각 선인장의 정점 수, 간선 수, 그리고 색상의 수를 의미합니다.

다음 $m$개의 줄에는 각각 선인장의 간선을 나타내는 두 정수 $u_i, v_i$ ($1 \le u_i \neq v_i \le n$)가 주어집니다. 주어진 그래프는 선인장이며, 임의의 두 정점 사이에는 최대 하나의 간선이 존재함이 보장됩니다.

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

출력

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

예제

입력 1

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

출력 1

9900
24