何老板给你一个简单无向图(无重边)。图中有$n$个点，$m$条边。点编号 \(1...n\)。一开始，图中的边都没有被涂色。
何老板有$k$种颜色的油漆。他打算给图中所有边涂色。
如果一个简单环(该环不会重复经过某个点)，设环上有$t$条边，按环的顺序依次编号为 \(e_1,e_2,...,e_t\) 。 何老板可以进行轮换涂色操作，即用原$e_1$的颜色去涂$e_2$，用原$e_2$的颜色去涂$e_3$,...,用原$e_t$的颜色去涂$e_1$。如下图所示：

如果一种涂色方案$A$通过轮换涂色操作能转换为另一种涂色方案$B$,何老板认为这两种方案本质是相同的。

何老板想知道，总共有多少种本质不同的涂色方案，答案 mod （10^9+7）

第一行三个正整数N M K
接下来M行每行两个正整数ai,bi表示图中的一条边。

输出一行一个非负整数表示答案。

$1≦N≦50$
$1≦M≦100$
$1≦K≦100$
$1≦ai,bi≦N(1≦i≦M)$
图中没有重边和自环