Andrei este în mare dificultate: se pare că are câteva probleme la şcoală. Prietenii lui s-au decis să-l mai înveselească şi i-au propus spre rezolvare o problemă la care se gândeau de mai mult timp. Problema cere numararea tuturor permutărilor cu N elemente care respectă următoarea proprietate: orice subsecvenţă pentru care elementele ei sunt atât în ordine crescătoare, cât şi consecutive are lungimea maxim K.
Cerinţă
Deoarece Andrei este ocupat, ajutaţi-l să determine numărul de permutări cu proprietatea cerută, modulo 30013.
Date de intrare
Pe prima linie a fişierului de intrare kcons.in se vor afla două numere naturale N şi K având semnificaţiile din enunţ.
Date de ieşire
În fişierul de ieşire kcons.out veţi afişa un singur număr reprezentând numărul de permutări cu proprietatea cerută, modulo 30013.
Restricţii
• 1 ≤ N ≤ 2000
• 1 ≤ K ≤ N
Exemple
kcons.in
kcons.out
Explicaţii
4 2
21
Din cele 24 de permutări posibile următoarele trei nu sunt bune: 1 2 3 4, 2 3 4 1, 4 1 2 3. Subsecvenţele subliniate conţin numere crescătoare şi consecutive, iar lungimea lor este mai mare decât 2.