cabane

Cabane

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

Poveste si cerinta...

Balaurul Arhirel este pus in fata unei mari dileme. Fara sa vrea, a ajuns in muntii Romaniei si trebuie sa parcurga un traseu de-a lungul caruia sa viziteze $N$ cabane. El poate porni de la orice cabana, dar trebuie sa treaca pe la fiecare cabana exact o data.
Cabanele sunt numerotate de la $1$ la $N$, iar fiecare se afla la o inaltime egala cu indicele sau exprimat in metri. Deplasarea intre oricare doua cabane se face in linie dreapta (creste sau scade constant). Problema este ca Balaurul nu poate urca sau cobori mai mult de $K$ metri intre oricare doua cabane consecutive de pe traseu, deci traseul trebuie sa fie bine ales.
Norocul Balaurului este ca exista multe posibilitati. Ghinionul vostru este ca Balaurul stie cate posibilitati sunt si vrea sa vada daca si voi stiti.
Pentru valorile $N$ si $K$ date, determinati numarul de posibilitati de a vizita fiecare dintre cele $N$ cabane exact o data, astfel incat diferenta de nivel (in valoare absoluta) dintre oricare doua cabane vizitate consecutiv sa fie de maxim $K$ metri. Rezultatul trebuie sa fie dat modulo $30103$ (restul impartirii la $30103$).

h2. Date de intrare

...

Fisierul de intrare $cabane.in$ va contine pe prima linie valorile $N$ si $K$ separate printr-un spatiu.

h2. Date de iesire

...

Fisierul de iesire $cabane.out$ va contine o singura linie pe care va fi scris numarul total de posibilitati modulo $30103$.

h2. Restrictii

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

* $K ≤ N ≤ 200$
* $1 ≤ K ≤ 6$

h2. Exemplu
table(example). |_. cabane.in |_. cabane.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 2
| 12

|
h3. Explicatie

...

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 4 2 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 ca intre cabana 1 si cabana 4 este o diferenta de 3 metri.
 

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

1857