지식 중심 문제

많은 지식을 쌓은 뒤 지식 중심의 문제를 하나 만들기로 했다. $n$개의 정점과 $m$개의 간선을 가진 무방향 그래프 $G$가 주어진다. 이 그래프를 $k$개 복사하여 $G_1, G_2, \ldots, G_k$라고 한다. 모든 $1 \le i \le k-1$과 모든 $1 \le u \le n$에 대해, 복사본 $G_i$의 정점 $u$와 $G_{i+1}$의 정점 $u$를 간선으로 잇는다. 이렇게 만든 새 그래프의 신장 트리 개수를 $10^9 + 7$로 나눈 나머지로 구한다.

첫 줄에 세 정수 $n$, $m$, $k$가 주어진다 ($1 \le n \le 500$, $0 \le m \le \frac{n(n-1)}{2}$, $1 \le k \le 10^{18}$). 다음 $m$개의 줄에는 무방향 간선 $(u, v)$를 나타내는 두 정수 $u$, $v$가 주어진다 ($1 \le u, v \le n$, $u \ne v$). 모든 간선은 서로 다르다.

새 그래프의 신장 트리 개수를 $10^9 + 7$로 나눈 나머지를 한 정수로 출력한다.