시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 256 MB 905 128 (14%) 113
문제
미르코는 그의 자유 시간을 색칠을 위해 사용하고 있다. 색칠을 하기 위해, 그는 붓과 $K$개의 색을 가지고 있는 팔레트를 사용하고 있다. 그의 친구 슬라브코는 미르코가 색칠을 얼마나 잘 하는지 보기 위해 색칠공부 책을 미르코에게 주었다. 색칠공부 책에는 $1, 2, \cdots, N$까지의 번호가 붙은 $N$개의 그림이 있다. 미르코는 슬라브코의 의도와는 다르게 한 그림은 팔레트에 있는 $K$개의 색 중에서 하나의 색만을 사용해서 칠하기로 결정했다. 그러나 미르코도 너무 밋밋한 것은 좋아하지 않기 때문에, $N$개의 정수 $f_i$를 선택하여 $i$번 그림은 $f_i$번 그림과는 다른 색으로 색칠을 하려고 한다. 단, $f_i = i$인 경우에는 다른 조건들을 만족한다면 $i$번 그림을 어떤 색으로 칠해도 상관이 없다. 미르코는 슬라브코가 준 색칠공부 책을 색칠할 수 있는 경우의 수가 몇 가지나 될 것인지 궁금해졌고, 당신에게 도움을 요청했다. 책을 색칠할 수 있는 경우의 수를 구하는 프로그램을 작성하라. 답이 매우 커질 수 있으므로, 답을 $1,000,000,007$으로 나눈 나머지를 출력한다.
입력
첫 번째 줄에 양의 정수 $N, K (1 \le N, K \le 1\,000\,000)$가 주어진다. 다음 줄에 $N$개의 정수 $f_i (1 \le f_i \le N)$가 주어진다. 전체 테스트 중의 50%는 $f_i$가 모두 다르다.
출력
첫 번째 줄에 슬라브코의 색칠공부 책을 색칠하는 경우의 수를 출력한다.
힌트
### 예제 #### 입력 1 ``` 2 3 2 1 ``` #### 출력 1 ``` 6 ``` 미르코는 세 가지 색을 가지고 있고 $1$번 그림과 $2$번 그림에 같은 색을 칠하지 않기로 했다. 가능 한 색칠하는 방법은 $(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)$으로 괄호 안에 있는 숫자 중에서 첫 번째 숫자는 $1$번 그림에 칠할 색, 두 번째 숫자는 $2$번 그림에 칠할 색을 나타낸다.
#### 입력 2 ``` 3 4 2 3 1 ``` #### 출력 2 ``` 24 ```
#### 입력 3 ``` 3 4 2 1 1 ``` #### 출력 3 ``` 36 ```
#### 입력 4 ``` 3 4 1 1 2 ``` #### 출력 4 ``` 36 ``` 미르코는 네 가지 색을 가지고 있다. $1$번 그림에는 아무런 제한이 없으므로 어떤 색으로 칠해도 상관이 없다. $2$번 그림 색은 $1$번 그림의 색과는 달라야 하고 $3$번 그림 색도 $2$번 그림의 색과는 달라야 한다. 즉 이 두 그림은 남아 있는 세 가지 색 중 하나로 칠해져야 한다는 뜻이다. 그렇기 때문에 색칠 할 수 있는 경우의 수는 36가지가 된다.