시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 126 | 21 | 13 | 31.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.
5 6 2 3 2 5 1 3 4 2 4 5 3 1 3
4725
2 1 200 1 2
272581704
5 10 1000000000000000000 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
569698435