/ 
Time Limit: 4 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
もうすぐみかんの誕生日である。あろまはグラフが好きなみかんのために今年も無向グラフをプレゼントすることにした。
あろまは n 頂点 n 辺からなる連結な無向グラフを購入した。このグラフの頂点には 1, 2, ..., n の番号がついており、各 i(1 \leq i \leq n) について頂点 i と頂点 a_i の間に辺がある。あろまは既製品を贈るだけでは芸がないと考え k 色で色を塗ることに決め、手始めに色の塗り方が何通りあるかを数えることにした。ただし、頂点番号を並び替えて一致する色の塗り方は同一であるとし、重複して数えないものとする。購入したグラフの頂点に 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)
- グラフは連結である。
- グラフに自己辺や多重辺は存在しない。
入力
入力は以下の形式で標準入力から与えられる。
n k a_1 : a_n
出力
グラフの頂点を k 色で塗る塗り方の個数を 10^9 + 7 で割った余りを一行で出力せよ。
入力例1
4 2 2 3 1 1
出力例1
12
入力例2
4 4 2 3 4 1
出力例2
55
入力例3
10 5 2 3 4 1 1 1 2 3 3 4
出力例3
926250
Score : 300 points
Problem Statement
Mikan's birthday is coming soon. Since Mikan likes graphs very much, Aroma decided to give her a undirected graph this year too.
Aroma bought a connected undirected graph, which consists of n vertices and n edges. The vertices are numbered from 1 to n and for each i(1 \leq i \leq n), vertex i and vartex a_i are connected with an undirected edge. Aroma thinks it is not interesting only to give the ready-made graph and decided to paint it. Count the number of ways to paint the vertices of the purchased graph in k colors modulo 10^9 + 7. Two ways are considered to be the same if the graph painted in one way can be identical to the graph painted in the other way by permutating the numbers of the vertices.
Constraints
- 1 \leq n \leq 10^5
- 1 \leq k \leq 10^5
- 1 \leq a_i \leq n (1 \leq i \leq n)
- The given graph is connected
- The given graph contains no self-loops or multiple edges.
Input
Each data set is given in the following format from the standard input.
n k a_1 : a_n
Output
Output the number of ways to paint the vertices of the given graph in k colors modulo 10^9 + 7 in one line.
Sample Input 1
4 2 2 3 1 1
Sample Output 1
12
Sample Input 2
4 4 2 3 4 1
Sample Output 2
55
Sample Input 3
10 5 2 3 4 1 1 1 2 3 3 4
Sample Output 3
926250