Road to top 50 V-N-U-S-E-R-S

Start

2022-01-01 02:00 AKST

Road to top 50 V-N-U-S-E-R-S

End

2022-01-05 06:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -141 days 15:20:07

Time elapsed

100:00:00

Time remaining

0:00:00

Problem R
Paleta

Little Mirko spends his free time painting. For this hobby, he likes to use brushes and a palette containing $K$ colors overall. His friend Slavko decided to use Mirko’s talent and gave him his new coloring book for Mirko to color. The coloring book contains $N$ images numbered $1, 2, \ldots , N$.

Mirko has decided to paint each image in exactly one color of the possible $K$ colors from his palette. However, he really likes colorful things. He chose $N$ numbers $f_ i$ and decided to paint the image numbered $i$ differently than the images numbered $f_ i$, except when $f_ i = i$. If $f_ i = i$, that means he can paint the image numbered $f_ i$ whichever color he likes, as long as all other conditions have been met.

Mirko wants to know the number of possible ways to color Slavko’s coloring book and he desperately needs your help! Calculate the number of possible ways to color the book. Given the fact that the output can be very large, print the answer modulo $1\, 000\, 000\, 007$.

Input

The first line of input contains positive integers $N$, $K$ ($1 \leq N, K \leq 1\, 000\, 000$). The following line contains N numbers $f_ i$ ($1 \leq f_ i \leq N$), as stated in the text.

Output

The first and only line must contain the number of possible ways to color Slavko’s book.

Sample Input 1 Sample Output 1
2 3
2 1
6
Sample Input 2 Sample Output 2
3 4
2 3 1
24
Sample Input 3 Sample Output 3
3 4
2 1 1
36