프로그램 명: coci_paleta
제한시간: 1 초

당신은 N개의 칸에 R개의 물감을 이용해서 색칠하려고 한다. 색칠을 같은 색으로만 하게 되면 밋밋하기 때문에 k번째 칸은 Fk 번째 칸과 다른 색으로 칠해야 한다. (단, k=Fk 이면 k번째 칸은 아무 색이나 칠해도 된다) 이 때, N개의 칸을 색칠하는 방법의 수를 구하여라.

입력 형식

전체 데이터의 50%는 Fk 가 모두 다르다.

출력 형식

N개의 칸을 색칠하는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

입출력 예 

입력 예 1
출력 예 1
2 3
2 1
6
입력 예 2
출력 예 2
3 4
2 3 1
24


입력 예 3
출력 예 3
3 4
2 1 1
36
입력 예 4
출력 예 4
3 4
1 1 2
36

입력 예 4 설명
첫 번째 칸을 색칠하는 방법은 4가지가 있다. 두 번째 칸은 첫 번째 칸과 다른 색으로 색칠해야 하므로 3가지 색 중 하나로 색칠할 수 있다. 세 번째 칸은 두 번째 칸과 다른 색으로 색칠해야 하므로 3가지 색 중 하나로 색칠할 수 있다. 따라서 3개의 칸을 색칠하는 방법의 수는 4x3x3 = 36이다.
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 fi and decided to paint the image numbered i differently than the images numbered fi , except when fi = i. If fi = i, that means he can paint the image numbered fi 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 ≤ N, K ≤ 1 000 000). Following line contains N numbers fi (1 ≤ fi ≤ N), the number stated in the text.

OUTPUT

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

SAMPLE TESTS 

ulaz 
 
2 3 
2 1 
 
izlaz 
 
6 
ulaz 
 
3 4 
2 3 1 
 
izlaz 
 
24 
ulaz 
 
3 4 
2 1 1 
 
izlaz 
 
36 
 
ulaz 
 
3 4 
1 1 2 
 
izlaz 
 
36 
Clarification of the first example: Mirko has three colors and decided that the image numbered 2 
mustn't be of the same color as the image numbered 1. The possible colorings are (1, 2), (1, 3), (2, 1), 
(2, 3), (3, 1), (3, 2), where the first number in the brackets represents the color of the first image and the 
second number the color of the second image. 
Clarification of the fourth example: Mirko has four colors. There are no conditions regarding the 
first image, it can be painted in whichever color. The second must be different than the first, and the 
third different than the second. That means that those two images can be colored in the remaining 3 
colors. This gives us a total of 36 combinations.

출처:coci/2013-2014/contest2 5번
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]