32212번 - 순열 제작의 달인

문제

배열 제작의 달인 Jiro는 길이 $N$인 수열 $A$가 주어졌을 때, 다음 조건을 만족하는 길이 $N$의 순열 $P$의 개수를 구하고자 한다. 길이 $N$의 순열 $P$는 1ドル$부터 $N$까지의 모든 정수를 한번만 사용하여 만든 수열을 의미한다.

• 수열 $B$는 $(A_{P_1},A_{P_2},...,A_{P_N})$로 정의한다.
• 수열 $B$의 가증스러움은 1ドル \le i \le N$인 정수 $i$에 대해 다음 조건을 만족하는 $i$의 개수로 정의한다.
  • $i=1$ 또는 $\max(B_1,...,B_{i-1}) < B_i$
• 수열 $B$의 가증스러움은 $K$ 이하이다.

Jiro가 조건을 만족하도록 구한 순열 $P$의 개수를 1ドル,000円,000円,007円$으로 나눈 나머지를 구하시오.

입력

첫째 줄에 수열 $A$의 길이 $N$와 조건에 명시된 $K$가 공백으로 구분되어 주어진다. $(1 \le N \le 5,000円$; 1ドル \le K \le N)$

둘째 줄에 수열 $A_1,ドル $A_2,ドル $\cdots,ドル $A_N$이 공백으로 구분되어 주어진다. $(1 \leq A_i \leq 10^9)$

출력

Jiro가 조건을 만족하도록 구한 순열 $P$의 개수를 1ドル,000円,000円,007円$으로 나눈 나머지를 출력한다.

제한

힌트