問題文

パ研合宿の運営リーダーである E869120 氏は、N 頂点 M 辺の連結な無向グラフを持っています。i 番目の辺は、頂点 a_i と b_i を結んでいます。

12 月 24 日、今日はクリスマスイブです。
そのため、彼はグラフに色を付け、パ研部長である reiji1112 氏にプレゼントすることを計画しました。
しかし、辺で直接隣り合う頂点が同じ色だと見栄えが良くないので、辺で直接隣り合う頂点同士は違う色で塗る必要があります。

色は K 色準備されています。色 1, 2, 3, ..., K と番号付けられています。
さて、塗り方は何通りあるでしょうか？ 1 \ 000 \ 000 \ 007 で割った余りを求めてください。

制約

• N は 1 以上 100 \ 000 以下の整数
• M は 1 以上 100 \ 003 以下の整数
• M - N は 3 以下である。
• K は 1 以上 1 \ 000 \ 000 \ 000 以下の整数
• a_i, b_i は 1 以上 N 以下の整数
• a_i < b_i (1 \leq i \leq M)
• (a_i, b_i) \neq (a_j, b_j) (i \neq j)

入力

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

N M K
a_1 b_1
a_2 b_2
a_3 b_3
...
a_M b_M

入力例 1

3 2 2
1 2
2 3

出力例 1

2

以下の 2 通りの塗り方が条件を満たします。

入力例 2

3 2 5
1 2
2 3

出力例 2

80

この入力例は小課題 1 の制約は満たしませんが、小課題 2 〜 8 の制約は満たします。

入力例 3

4 3 1
1 2
2 3
2 4

出力例 3

0

入力例 4

6 5 4
1 2
1 3
2 4
2 5
3 6

出力例 4

972

入力例 5

10 10 100
1 2
1 3
2 4
2 5
2 6
2 7
3 8
5 9
9 10
4 8

出力例 5

332858118

答えを 1 \ 000 \ 000 \ 007 で割った余りを求めてください。