색칠 공부

상근이는 시간이 날 때마다 색칠 공부를 한다. 상근이에게는 색이 $K$가지 담긴 팔레트와 붓 한 자루가 있다. 친구 선영이는 생일 선물로 색칠 공부 책을 줬다. 책에는 그림이 $N$개 있고, 1번부터 $N$번까지 번호가 붙어 있다.

상근이는 그림마다 $K$가지 색 중 하나를 골라 칠하려고 한다. 선영이는 화려한 것을 좋아해서 숫자 $N$개 $f_1, f_2, \dots, f_N$을 정해 줬다. 상근이는 $i$번 그림을 $f_i$번 그림과 다른 색으로 칠해야 한다. $i$와 $f_i$가 같으면 $i$번 그림은 아무런 제한 없이 칠할 수 있다.

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

첫째 줄에 $N$과 $K$가 주어진다. ($1 \le N, K \le 1{,}000{,}000$)

둘째 줄에 숫자 $N$개 $f_1, f_2, \dots, f_N$이 주어진다. ($1 \le f_i \le N$)

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

$N = 2$, $K = 3$, $f = (2, 1)$인 경우 1번 그림과 2번 그림을 같은 색으로 칠할 수 없다. 두 그림에 칠한 색을 순서쌍으로 적으면 (1,2), (1,3), (2,1), (2,3), (3,1), (3,2)의 여섯 가지다.