kcons

Kcons

== include(page="template/taskheader" task_id="kcons") ==

Poveste şi cerinţă...

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 numărarea 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$.
 
Deoarece Andrei este ocupat, ajutaţi-l să determine numărul de permutări cu proprietatea cerută, modulo $30013$.

h2. Date de intrare

Fişierul de intrare $kcons.in$ ...

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ţ.

h2. Date de ieşire

În fişierul de ieşire $kcons.out$ ...

Î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$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 2000$
* $1 ≤ K ≤ N$
* Pentru $10%$ din teste $N ≤ 10$
* Pentru $50%$ din teste $N ≤ 70$
* Pentru $70%$ din teste $N ≤ 300$
* Pentru $40%$ din teste $K = 1$

h2. Exemplu

table(example). |_. kcons.in |_. kcons.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

table(example). |_. kcons.in |_. kcons.out |_. kcons.in |_. kcons.out |
| 4 2
| 21
| 25 10
| 27042
|

h3. Explicaţie

...

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.
 

== include(page="template/taskfooter" task_id="kcons") ==

4892