시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 11 | 5 | 3 | 33.333% |
You are given a directed graph which is constructed as follows:
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:
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.
6 3 2 3 4 1 1 3
378