Fişierul intrare/ieşire:	kcons.in, kcons.out	Sursă	Lot Vrancea 2010, Baraj 1
Autor	Adrian Airinei, Cosmin Gheorghe	Adăugată de	Andrei Misarca •Mishu91
Timp execuţie pe test	0.125 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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

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
• Pentru 10% din teste N ≤ 10
• Pentru 50% din teste N ≤ 70
• Pentru 70% din teste N ≤ 300
• Pentru 40% din teste K = 1

Exemplu

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.

Cum se trimit solutii?