AT_pakencamp_2018_day2_g グランド・グラフ　(Grand Graph)

[problemUrl]: https://atcoder.jp/contests/pakencamp-2018-day2/tasks/pakencamp_2018_day2_g パ研合宿の運営リーダーである $ E869120 $ 氏は、$ N $ 頂点 $ M $ 辺の連結な無向グラフを持っています。$ i $ 番目の辺は、頂点 $ a_i $ と $ b_i $ を結んでいます。 $ 12 $ 月 $ 24 $ 日、今日はクリスマスイブです。 そのため、彼はグラフに色を付け、パ研部長である $ reiji1112 $ 氏にプレゼントすることを計画しました。 しかし、辺で直接隣り合う頂点が同じ色だと見栄えが良くないので、辺で直接隣り合う頂点同士は違う色で塗る必要があります。 色は $ K $ 色準備されています。色 $ 1 $, $ 2 $, $ 3 $, ..., $ K $ と番号付けられています。 さて、塗り方は何通りあるでしょうか？ $ 1\ 000\ 000\ 007 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ M $ $ K $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ a_3 $ $ b_3 $ ... $ a_M $ $ b_M $

グラフの塗り方は何通りあるか、$ 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\