题目描述

シカのAtCoDeerくんはある日、 $N$ 頂点 $M$ 辺からなる単純な(すなわち、多重辺と自己ループのない)グラフを拾いました。頂点には$1$,$2$,$..$,$N$の番号がついていて互いに区別が可能で、辺は$(a_i,b_i)\ (1≦i≦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$ で割ったあまりを出力してください。

输入格式

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

$N$ $M$ $K$ $a_1$ $b_1$ $a_2$ $b_2$ $:$ $a_M$ $b_M$

输出格式

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

题目大意

给定一张$N$个点$M$条边的无向图，每条边要染一个编号在$1$到$K$的颜色。

你可以对一张染色了的图进行若干次操作，每次操作形如，在图中选择一个简单环（即不经过相同点的环），并且将其颜色逆（顺）时针旋转一个单位。

两种染色方案被认为是本质相同的，当且仅当其中一种染色后的图经过若干次操作后可以变成另一种染色后的图。

问有多少本质不同的染色方案，输出对$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

提示

制約

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