AT_kupc2016_j 色塗り

[problemUrl]: https://atcoder.jp/contests/kupc2016/tasks/kupc2016_j もうすぐみかんの誕生日である。あろまはグラフが好きなみかんのために今年も無向グラフをプレゼントすることにした。 あろまは $ n $ 頂点 $ n $ 辺からなる連結な無向グラフを購入した。このグラフの頂点には $ 1,\ 2,\ ...,\ n $ の番号がついており、各 $ i $$ (1\ \leq\ i\ \leq\ n) $ について頂点 $ i $ と頂点 $ a_i $ の間に辺がある。あろまは既製品を贈るだけでは芸がないと考え $ k $ 色で色を塗ることに決め、手始めに色の塗り方が何通りあるかを数えることにした。**ただし、頂点番号を並び替えて一致する色の塗り方は同一であるとし、重複して数えないものとする。**購入したグラフの頂点に $ k $ 色で塗る塗り方の個数を $ 10^9\ +\ 7 $ で割った余りを求めよ。

入力は以下の形式で標準入力から与えられる。 > $ n $ $ k $ $ a_1 $ : $ a_n $

グラフの頂点を $ k $ 色で塗る塗り方の個数を $ 10^9\ +\ 7 $ で割った余りを一行で出力せよ。

### 制約 - $ 1\ \leq\ n\ \leq\ 10^5 $ - $ 1\ \leq\ k\ \leq\ 10^5 $ - $ 1\ \leq\ a_i\ \leq\ n $ $ (1\ \leq\ i\ \leq\ n) $ - グラフは連結である。 - グラフに自己辺や多重辺は存在しない。