Description

Mirko has $k$ colors and $n$ pictures that need to be colored. The pictures are numbered from $1$ to $n$, and he decided to fill each picture using one of the $k$ colors.

To do this, he chose $n$ numbers $f_i$, and decided to color the pictures in the following way:

• If $f_i\ne i$, then the color of picture $i$ must not be the same as the color of picture $f_i$.
• If $f_i=i$, then as long as all other conditions are satisfied, he may color picture $f_i$ with any color.

You need to find the number of possible ways to color the pictures.

Since the output may be very large, you only need to output the answer modulo $\bm{10^9+7}$.

Input Format

The first line contains two integers $n, k$, representing the number of pictures and the number of colors.

The next $n$ lines each contain $f_i$.

Output Format

Output a single integer: the number of possible ways to color the pictures modulo $10^9+7$.

2 3
2 1

6

3 4
2 3 1

24

3 4
2 1 1

36

3 4
1 1 2

36

Hint

Explanation for Sample 1

There are $3$ colors, and the color of picture $2$ must not be the same as the color of picture $1$. The possible colorings are $(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)$, where the two numbers in parentheses represent the colors of the two pictures.

Explanation for Sample 4

There are $4$ colors.

• For picture $1$, it can be colored with any color.
• For picture $2$, its color must not be the same as the color of picture $1$.
• For picture $3$, its color must not be the same as the color of picture $2$.

That is, picture $2$ can be colored in $3$ ways excluding the color of picture $1$, and picture $3$ can be colored in $3$ ways excluding the color of picture $2$.

The answer is $4\times 3\times 3=36$.

Constraints

• For $50\%$ of the testdata, $f_i\ne f_j(1\le i\ne j\le n)$.
• For $100\%$ of the testdata, $1\le n,k\le 10^6$.

For all valid $f_i$, $1\le f_i\le n$.

Source

This problem is translated from COCI2013-2014 CONTEST 2 T5 PALETA.

According to the original testdata settings, the full score of this problem is $140$ points.

Translated by ChatGPT 5