配点 : $1300$ 点

問題文

シカのAtCoDeerくんはある日、 $N$ 頂点 $M$ 辺からなる単純な(すなわち、多重辺と自己ループのない)グラフを拾いました。頂点には$1$,$2$,$..$,$N$の番号がついていて互いに区別が可能で、辺は$(a_i,b_i) (1 \leq i \leq M)$で表されます。 AtCoDeerくんは $K$ 色のペンキを使って各辺を塗ろうとしています。ペンキは大量にあるので同じ色で複数の辺を塗ることが可能です。 AtCoDeerくんの拾ったグラフは特殊な形状をしているため、単純なサイクル(すなわち,サイクルであって同じ頂点を一度しか通らないもの)を選んで、そのサイクル上の辺の色をひとつずつサイクルに沿ってずらすことが出来ます。正確に言うと、サイクル上の辺を順に $e_1$, $e_2$,$..$,$e_a$ とすると、 $e_1$ に塗られていた色を $e_2$ に、$e_2$ に塗られていた色を $e_3$ に、 $...$、 $e_{a-1}$ に塗られていた色を $e_a$ に、$e_a$ に塗られていた色を $e_1$ に、同時に塗り替えることが出来ます。

図$1$: 操作の例

塗り方Aと塗り方Bは、この操作を有限回行ってAからBに変形できるときに同じ塗り方だとみなします。グラフの塗り方が何通りあるか求めてください。ただしこの数は非常に大きくなることがあるので、 $10^9+7$ で割ったあまりを出力してください。

制約

• $1 \leq N \leq 50$
• $1 \leq M \leq 100$
• $1 \leq K \leq 100$
• $1 \leq a_i,b_i \leq N (1 \leq i \leq M)$
• グラフには自己ループや多重辺はない。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$

$a_1$ $b_1$

$a_2$ $b_2$

$:$

$a_M$ $b_M$

出力

塗り方が何通りあるかを $10^9+7$ で割ったあまりを出力せよ。

4 4 2
1 2
2 3
3 1
3 4

8

5 2 3
1 2
4 5

9

11 12 48
3 1
8 2
4 9
5 4
1 6
2 9
8 3
10 8
4 10
8 6
11 7
1 8

569519295