Coloring Book

Sanggeun colors pictures whenever he has spare time. He has a palette holding $K$ colors and one brush. His friend Seonyeong gave him a coloring book for his birthday. The book has $N$ pictures, numbered 1 through $N$.

Sanggeun wants to paint every picture with one of the $K$ colors. Seonyeong likes flashy results, so she fixed $N$ numbers $f_1, f_2, \dots, f_N$. Picture $i$ must be painted a different color from picture $f_i$. When $i$ and $f_i$ are the same, picture $i$ can be painted with no restriction.

Given $N$, $K$, and every $f_i$, write a program that counts the ways Sanggeun can color the book.

The first line contains $N$ and $K$. ($1 \le N, K \le 1{,}000{,}000$)

The second line contains the $N$ numbers $f_1, f_2, \dots, f_N$. ($1 \le f_i \le N$)

Print the number of ways to color the coloring book on the first line. The count gets very large, so print it modulo $1{,}000{,}000{,}007$.

When $N = 2$, $K = 3$, and $f = (2, 1)$, pictures 1 and 2 cannot take the same color. Writing the two colors as an ordered pair, the six possibilities are (1,2), (1,3), (2,1), (2,3), (3,1), (3,2).