| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 5 | 5 | 5 | 100.000% |
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$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $K = 1$ |
| 2 | 15 | $K = 2$ |
| 3 | 12 | $N ≤ 10$ |
| 4 | 24 | $N ≤ 100$ |
| 5 | 16 | $N ≤ 300$ |
| 6 | 23 | nema dodatnih ograničenja |
5 1
26
4 2
11
10 7
47840
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]$