시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB126211331.707%

문제

After gaining a lot of knowledge, you decided to write a knowledge-oriented problem.

You are given an undirected graph G with n vertices and m edges. You copy it k times and denote the copies by G1, G2, . . . , Gk. You add edges between vertex u in copy Gi and the same vertex u in copy Gi+1 for all 1 ≤ i ≤ k−1 and 1 ≤ u ≤ n.

Find the number of spanning trees of the new graph. The answer can be large, so output it modulo 109 + 7.

입력

The first line contains three integers n, m, k (1 ≤ n ≤ 500, 0 ≤ m ≤ n(n−1)/2, 1 ≤ k ≤ 1018).

Each of the following m lines contains two integers u, v (1 ≤ u, v ≤ n, u ≠ v) indicating an undirected edge (u, v) in the graph. All edges are distinct.

출력

Output one integer: the answer.

예제 입력 1

5 6 2
3 2
5 1
3 4
2 4
5 3
1 3

예제 출력 1

4725

예제 입력 2

2 1 200
1 2

예제 출력 2

272581704

예제 입력 3

5 10 1000000000000000000
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

예제 출력 3

569698435