Balaurul Arhirel este pus în faţa unei mari dileme. Fără să vrea, a ajuns în munţii României şi trebuie să parcurgă un traseu de-a lungul căruia să viziteze N cabane. El poate porni de la orice cabană, dar trebuie să treacă pe la fiecare cabană exact o dată.
Cabanele sunt numerotate de la 1 la N, iar fiecare se află la o înălţime egală cu indicele său exprimat în metri. Deplasarea între oricare două cabane se face în linie dreaptă (creşte sau scade constant). Problema este că Balaurul nu poate urca sau coborî mai mult de K metri între oricare două cabane consecutive de pe traseu, deci traseul trebuie să fie bine ales.
Norocul Balaurului este că există multe posibilităţi. Ghinionul vostru este că Balaurul ştie câte posibilităţi sunt şi vrea să vadă dacă şi voi ştiţi.
Cerinţă
Pentru valorile N şi K date, determinaţi numărul de posibilităţi de a vizita fiecare dintre cele N cabane exact o dată, astfel încât diferenţa de nivel (în valoare absolută) dintre oricare două cabane vizitate consecutiv să fie de maxim K metri. Rezultatul trebuie să fie dat modulo 30103 (restul împărţirii la 30103).
Date de intrare
Fişierul de intrare cabane.in va conţine pe prima linie valorile N şi K separate printr-un spaţiu.
Date de ieşire
Fişierul de ieşire cabane.out va conţine o singură linie pe care va fi scris numărul total de posibilităţi modulo 30103.
Restricţii
• K ≤ N ≤ 200
• 1 ≤ K ≤ 6
Exemple
cabane.in
cabane.out
Explicaţii
4 2
12
Din cele 24 de trasee posibile 12 sunt valide: 1 2 3 4, 1 2 4 3, 1 3 2 4, 1 3 4 2,
2 1 3 4, 2 4 3 1, 3 1 2 4, 3 2 4 1,
4 2 1 3, 4 2 3 1, 4 3 1 2, 4 3 2 1
Iar celelalte 12 nu sunt. De exemplu 2 1 4 3 nu e valid pentru că între cabana 1 şi cabana 4 este o diferenţă de 3 metri.