문제
당신은 N개의 칸에 R개의 물감을 이용해서 색칠하려고 한다.
색칠을 같은 색으로만 하게 되면 밋밋하기 때문에 k번째 칸은 Fk 번째 칸과 다른 색으로 칠해야 한다. (단, k=Fk 이면 k번째 칸은 아무 색이나 칠해도 된다)
이 때, N개의 칸을 색칠하는 방법의 수를 구하여라.
입력
첫 번째 줄에는 칸의 수 N과 물감의 수 R이 주어진다. (1 ≤ N, R ≤ 1,000,000)
두 번째 줄에는 N개의 Fk 가 주어진다. (1 ≤ Fk ≤ N) 전체 데이터의 50%는 Fk 가 모두 다르다.
출력
N개의 칸을 색칠하는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.
예제1
입력
2 3
2 1
출력
6
첫 번째 칸은 두 번째 칸(F1)과 같지 않아야 하고 두 번째 칸은 첫 번째 칸(F2)과 같지 않아야한다. 가능한 경우는 (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2) 6가지이다.
예제2
입력
3 4
2 3 1
출력
24
예제3
입력
3 4
2 1 1
출력
36
예제4
입력
3 4
1 1 2
출력
36
첫 번째 칸을 색칠하는 방법은 4가지가 있다.
두 번째 칸은 첫 번째 칸과 다른 색으로 색칠해야 하므로 3가지 색 중 하나로 색칠할 수 있다.
세 번째 칸은 두 번째 칸과 다른 색으로 색칠해야 하므로 3가지 색 중 하나로 색칠할 수 있다.
따라서 3개의 칸을 색칠하는 방법의 수는 4x3x3 = 36이다.
힌트
출처
COCI 2013/2014 - Contest 2