\(2^{nd}\) round, November \(9^{th}\), 2013

Little Mirko spends his free time painting. For this hobby, he likes to use brushes and a pallet
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, ..., N.

Mirko has decided to paint each image in exactly one color of the possible K colors from his pallet.
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.

In test data worth 50% of total points, all numbers f_{i} will be different.

The first line of input contains positive integers N, K (\(1 \le N\), \(K \le 1\,000\,000\)).
Following line contains N numbers f_{i}(\(1 \le f_{i} \le N\)), the number stated in the text.

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

생성자가 기록되지 않았습니다.

출처 COCI 2013/2014 Contest 2