19466번 - Colored Graphs 다국어

문제

You are given a directed graph which is constructed as follows:

• Pick a connected undirected graph with exactly $n$ vertices and $n$ edges. The vertices are numbered 1ドル$ through $n$.
• Convert each undirected edge into a directed edge in such a way that each vertex has outdegree 1ドル$.

Additionally, you are given $m$ different colors to color the vertices. Your task is to calculate the number of different colored graphs that can be made.

Two colored graphs $A$ and $B$ are considered the same if and only if there exists a mapping $P$ between their sets of vertices which satisfies the following constraints:

• Vertex $u$ in graph $A$ has the same color as vertex $P (u)$ in graph $B$.
• For any two different vertices $u$ and $v$ in graph $A,ドル $P (u)$ and $P (v)$ are different vertices in graph $B$.
• For any directed edge $u \to v$ in graph $A,ドル there exists a corresponding directed edge $P (u) \to P (v)$ in graph $B$.

Print the answer modulo 10ドル^9 + 7$.

입력

The first line of the input contains two space-seperated integers $n$ and $m$ (3ドル \le n \le 10^5,ドル 1ドル \le m \le 10^9$), representing the number of vertices in the graph and the number of colors you have.

Then, $n$ lines follow. The $i$-th of them contains an integer $f_i$ (1ドル \le f_i \le n,ドル $f_i \ne i$), denoting a directed edge from vertex $i$ to vertex $f_i$ in the given graph.

출력

Print a single line containing the answer.

제한

힌트