Problem Description

Mirko has $k$ colors and $n$ images to be colored. The images are numbered from $1$ to $n$, and he decides to fill each image with one of the $k$ colors.

To do this, he selects $n$ numbers $f_i$ and decides to color them according to the following rules:

• If $f_i \ne i$, then the color of image $i$ should not be the same as the color of image $f_i$.
• If $f_i = i$, he can color image $f_i$ with any color as long as all other conditions are met.

You need to find the number of possible coloring methods.

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

Input Format

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

The next $n$ lines contain the numbers $f_i$.

Output Format

A single line containing one integer, which is the number of possible coloring methods modulo $10^9+7$.

Sample Input and Output

Sample Input #1

2 3
2 1

Sample Output #1

6

Sample Input #2

3 4
2 3 1

Sample Output #2

24

Sample Input #3

3 4
2 1 1

Sample Output #3

36

Sample Input #4

3 4
1 1 2

Sample Output #4

36

Notes

Sample 1 Explanation

There are $3$ colors, and the color of image $2$ cannot be the same as the color of image $1$. Possible coloring schemes are $(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)$, where the numbers in the parentheses represent the colors of the two images.

Sample 4 Explanation

There are $4$ colors.

• For image $1$, it can be colored with any color.
• For image $2$, the color cannot be the same as the color of image $1$.
• For image $3$, the color cannot be the same as the color of image $2$.

Thus, image $2$ can be colored with $3$ colors other than the color of image $1$, and image $3$ can be colored with $3$ colors other than the color of image $2$.

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

Data Constraints

• For $50\%$ of the data, $f_i \ne f_j (1 \le i \ne j \le n)$.
• For $100\%$ of the data, $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 problem data configuration, this problem is worth $140$ points.

见题面 Input 部分

见题面 Output 部分