在获得了大量知识后，你决定编写一道面向知识的问题。

给定一个包含 $n$ 个顶点和 $m$ 条边的无向图 $G$。你将其复制 $k$ 次，并将这些副本记为 $G_1, G_2, \dots, 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$ ($1 \le u, v \le n, u \neq v$)，表示图中存在一条无向边 $(u, v)$。所有边均不相同。

输出格式

输出一个整数：答案。

样例

输入 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