문제
당신은 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
입력
23
21
출력
6
첫 번째 칸은 두 번째 칸(F1)과 같지 않아야 하고 두 번째 칸은 첫 번째 칸(F2)과 같지 않아야한다. 가능한 경우는 (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2) 6가지이다.
예제2
입력
34
231
출력
24
예제3
입력
34
211
출력
36
예제4
입력
34
112
출력
36
첫 번째 칸을 색칠하는 방법은 4가지가 있다.
두 번째 칸은 첫 번째 칸과 다른 색으로 색칠해야 하므로 3가지 색 중 하나로 색칠할 수 있다.
세 번째 칸은 두 번째 칸과 다른 색으로 색칠해야 하므로 3가지 색 중 하나로 색칠할 수 있다.
따라서 3개의 칸을 색칠하는 방법의 수는 4x3x3 = 36이다.
힌트
출처
COCI 2013/2014 - Contest 2