Coloring Book

Time limit1sMemory limit128 MB

Summary

Count the assignments of K colors to N pictures so each picture i differs from picture f_i unless f_i equals i, modulo 1,000,000,007.

Level: Medium6 of 10
Topics: Graph, Combinatorics, Math
Solved: No attempts yet

Problem

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.

Input

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$ )

Output

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

Hint

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).

Examples4

Example 1
Input
```
2 3
2 1
```
Expected output
```
6
```
Example 2
Input
```
3 4
2 3 1
```
Expected output
```
24
```
Example 3
Input
```
3 4
2 1 1
```
Expected output
```
36
```
Example 4
Input
```
3 4
1 1 2
```
Expected output
```
36
```