kcons

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 $30 \ 013$.

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 $30 \ 013$.

Restricții și precizări

• $1 \leq N \leq 2 \ 000$;
• $1 \leq K \leq N$;
• Pentru $10\%$ din teste $N \leq 10$
• Pentru $50\%$ din teste $N \leq 70$
• Pentru $70\%$ din teste $N \leq 300$

Exemplul 1

kcons.in

4 2

kcons.out

21

Explicație

Din cele $24$ de permutări posibile următoarele trei nu sunt bune: $(\underline{1 \ 2 \ 3 \ 4})$, $(\underline{2 \ 3 \ 4} \ 1)$, $(4 \ \underline{1 \ 2 \ 3})$. Subsecvenţele subliniate conţin numere crescătoare şi consecutive, iar lungimea lor este mai mare decât $2$.

Exemplul 2

kcons.in

25 10

kcons.out

27042