Dim

시간 제한1초메모리 제한2048 MB

요약

길이 N인 순열 중 정확히 K개의 내림(디미차)을 가진 순열의 개수를 10^9+7로 나눈 나머지를 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

Permutacija je niz od $N$ elemenata koji čine međusobno različiti prirodni brojevi od $1$ do $N$ , gdje je $N$ prirodni broj. Uz pojam permutacije, definiramo pojam dimice.

Par uzastopnih elemenata permutacije takvih da je lijevi element tj. onaj element koji se prije pojavljuje u permutaciji veći od desnog elementa. Npr. permutacija $\[2, 5, 4, 1, 6, 3]$ ima $3$ dimice: $(5, 4)$ , $(4, 1)$ i $(6, 3)$ .

Marko jako voli permutacije. Izabrao je broj $N$ , duljinu permutacije, i broj $K$ , broj dimica u permutaciji.

Želi zapisati sve permutacije duljine $N$ koje imaju točno $K$ dimica, ali htio bih znati koliko uopće ima takvih permutacija. Pomognite Marku i odgovorite mu na pitanje.

입력

U prvom retku se nalaze nenegativni cijeli brojevi $N$ i $K$ ( $1 ≤ N ≤ 5000$ , $0 ≤ K ≤ N - 1$ ).

출력

U prvi i jedini redak, ispišite cijeli broj, ostatak pri dijeljenju odgovora na pitanje s $10^9 + 7$ .

힌트

Opis drugog probnog primjera: Permutacije duljine četiri koje imaju dvije dimice su sljedeće: $\[1, 2, 4, 3]$ , $\[1, 3, 2, 4]$ , $\[1, 3, 4, 2]$ , $\[1, 4, 2, 3]$ , $\[2, 1, 3, 4]$ , $\[2, 3, 1, 4]$ , $\[2, 3, 4, 1]$ , $\[2, 4, 1, 3]$ , $\[3, 1, 2, 4]$ , $\[3, 4, 1, 2]$ , $\[4, 1, 2, 3]$

예제3

예제 1
입력
```
5 1
```
예상 출력
```
26
```
예제 2
입력
```
4 2
```
예상 출력
```
11
```
예제 3
입력
```
10 7
```
예상 출력
```
47840
```