COCI 2013/2014 - Contest 2- 색칠(PALETA) > 문제은행 : 정보올림피아드&알고리즘




2670 : 색칠(PALETA)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
15 회   
시도횟수
121 회   

문제

당신은 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로 나눈 나머지를 출력한다.

입력 예

2 3
2 1

출력 예

6

입력 예

3 4
2 3 1

출력 예

24

입력 예

3 4
2 1 1

출력 예

36

입력 예

3 4
1 1 2

출력 예

36

Hint!

입력 예1 첫 번째 칸은 두 번째 칸(F1)과 같지 않아야 하고 두 번째 칸은 첫 번째 칸(F2)과 같지 않아야한다. 가능한 경우는 (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2) 6가지이다. 입력 예4 첫 번째 칸을 색칠하는 방법은 4가지가 있다. 두 번째 칸은 첫 번째 칸과 다른 색으로 색칠해야 하므로 3가지 색 중 하나로 색칠할 수 있다. 세 번째 칸은 두 번째 칸과 다른 색으로 색칠해야 하므로 3가지 색 중 하나로 색칠할 수 있다. 따라서 3개의 칸을 색칠하는 방법의 수는 4x3x3 = 36이다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP