P7752 [COCI 2013/2014 #2] PALETA

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}$.**

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 a single integer: the number of possible ways to color the pictures modulo $10^9+7$.

#### 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](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 2](https://hsin.hr/coci/archive/2013_2014/contest2_tasks.pdf) _T5 PALETA_.** According to the original testdata settings, the full score of this problem is $140$ points. Translated by ChatGPT 5