26614번 - 주고받기

경기과학고에 재학 중인 $N$명의 학생들은 연말마다 선물을 주고받는 기념비적인 행사를 진행한다. 학교에서 주관하는 중요한 행사인 만큼, 모두가 참여하여 미리 선물을 준비하고 전달한다. 그러나 선물을 받지 못해 슬퍼하는 학생이 있어서는 안 되기 때문에 아래와 같은 세 가지 기본 규칙이 있다.

1. 모든 학생은 처음에 각자 하나의 선물을 준비한다.
2. $1 \leq i \leq N$을 만족하는 모든 정수 $i$에 대해, $i$번 학생은 $1$ 이상 $N$ 이하의 정수 $A_{i}$을 골라 둔다. 이때, 서로 다른 학생은 다른 정수를 골라야 한다.
3. 모든 학생이 동시에 선물을 주고받는다. 구체적으로, $i$번 학생은 $A_{i}$번 학생에게 지금 가지고 있는 선물을 준다. 2번 규칙에 의해, $i$번 학생은 $A_{j}=i$를 만족하는 유일한 $j$번 학생으로부터 선물을 받는다는 것을 알 수 있다.

물론 $A_{i}=i$여서 $i$번 학생이 자신에게 선물을 주는 것도 가능하다.

경기과학고의 행사 관리자인 여러분은 위 규칙이 완벽하다고 생각했기 때문에, 규칙을 따로 바꾸지 않고 몇 년 동안 행사를 그대로 이어 왔다. 그러나 행사의 만족도는 점차 떨어졌고 작년의 만족도 조사에서는 대부분의 학생들이 '이 행사의 의미를 잘 모르겠다'라고 답했다. 이유를 물어 보니, 누구한테서 선물을 받을지가 너무 뻔하다는 것이었다. 따라서 올해는 학생들에게 알리지 않은 채로 아래 규칙을 추가해서 행사를 진행했다.

• 3번 규칙을 총 $K$번 반복한다.

그러자 $i$번 학생이 처음 가지고 있던 선물은 $B_{i}$번 학생에게로 가게 되었고, 모든 학생은 신선하다며 높은 만족도를 보였다. 여러분 또한 새로운 규칙에 만족했다. 그러다 문득 각 학생이 2번 규칙에서 어떤 수를 골랐는지 알고 싶어졌다. $i$번 학생이 처음 가지고 있던 선물을 최종적으로 받게 된 학생의 번호 $B_{i}$들의 배열 $[B_{1}, B_{2}, ..., B_{N}]$이 주어졌을 때, $i$번 학생이 2번 규칙에서 고른 자연수 $A_{i}$들의 배열 $[A_{1}, A_{2}, ..., A_{N}]$로 가능한 것의 개수를 구해 보자.

첫 번째 줄에 두 양의 정수 $N$, $K$가 공백을 사이에 두고 주어진다. $(1 \le N, K \le 1000)$

두 번째 줄에는 $N$개의 양의 정수가 공백을 사이에 두고 주어진다. $i$번째 수는 $i$번 학생이 처음 가지고 있던 선물을 최종적으로 받게 된 학생의 번호 $B_{i}$를 의미한다. $(1 \le B_{i} \le N)$

첫 번째 줄에 $i$번 학생이 고른 자연수 $A_{i}$들의 배열 $[A_{1}, A_{2}, ..., A_{N}]$으로 가능한 것의 개수를 $10^9+7$로 나눈 나머지를 출력한다.