cabane

Cabane

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

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 să viziteze $N$ cabane. El poate porni de la orice cabana, dar trebuie sa treaca pe la fiecare cabană exact o data.

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 că exista multe posibilitati. Ghinionul vostru este că 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 să fie de maxim $K$ metri. Rezultatul trebuie sa fie dat modulo $30103$ (restul impartirii la $30103$).

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

|
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 2 4 1,$

$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