#arc062d. [arc062_d]Painting Graphs with AtCoDeer

[arc062_d]Painting Graphs with AtCoDeer

問題文

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

11: 操作の例

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

制約

  • 1N501≦N≦50
  • 1M1001≦M≦100
  • 1K1001≦K≦100
  • 1ai,biN(1iM)1≦a_i,b_i≦N (1≦i≦M)
  • グラフには自己ループや多重辺はない。

入力

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

NN MM KK a1a_1 b1b_1 a2a_2 b2b_2 :: aMa_M bMb_M

出力

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


入力例 1

4 4 2
1 2
2 3
3 1
3 4

出力例 1


入力例 2

5 2 3
1 2
4 5

出力例 2


入力例 3

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

出力例 3

569519295