시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 95 22 21 28.378%

문제

상근이는 시간이 날 때마다 색칠 공부를 하고 있다. 상근이는 총 K개의 색이 담겨있는 팔레트를 가지고 있고, 붓을 이용해 색칠을 한다. 상근이의 친구 선영이는 상근이의 생일 선물로 색칠 공부 책을 선물했다. 책에는 그림이 총 N개 있으며, 1번부터 N번까지 번호가 붙여져 있다.

상근이는 각각의 그림을 K가지 색 중 하나를 골라 색칠하려고 한다. 선영이는 화려한 것을 좋아하기 때문에 상근이에게 숫자 N개 fi를 정해주었다. 상근이는 i번 그림을 fi번 그림과 다른 색으로 색칠해야 한다. i가 fi가 같은 경우에 아무런 제한없이 i번 그림을 색칠할 수 있다.

N과 K, 그리고 fi가 모두 주어졌을 때, 상근이가 색칠 공부 책을 색칠하는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 1,000,000) 둘째 줄에는 숫자 N개 fi가 주어진다. (1 ≤ fi ≤ N)

출력

첫째 줄에 색칠 공부 책을 색칠하는 방법의 수를 출력한다. 방법의 수가 매우 많기 때문에 1,000,000,007로 나눈 나머지를 출력한다. 

예제 입력

2 3
2 1

예제 출력

6

힌트

1번 그림과 2번 그림은 서로 같은 색으로 색칠하면 안된다. 따라서 가능한 방법은 (1,2), (1,3), (2,1), (2,3), (3,1), (3,2)가 있다.