bobo 有一个连通图 $G$，他想用 $c$ 种颜色中的一种为每个顶点着色，使得没有两个相邻的顶点具有相同的颜色。
求着色方案数，结果对 $(10^9 + 7)$ 取模。
输入格式
第一行包含 3 个整数 $n, m, c$，分别表示顶点数、边数和颜色数（$1 \le n \le 10^5, n - 1 \le m \le n + 8, 1 \le c \le 10^9$）。
顶点编号为 $1, 2, \dots, n$。
接下来的 $m$ 行，每行包含 2 个整数 $a_i, b_i$，表示顶点 $a_i$ 和 $b_i$ 之间的一条边（$1 \le a_i, b_i \le n, a_i \neq b_i$）。
输出格式
输出一个整数，表示着色方案数。
样例
样例输入 1
3 3 3 1 2 2 3 3 1
样例输出 1
6
样例输入 2
4 3 1000000000 1 2 2 3 3 4
样例输出 2
3584