== include(page="template/taskheader" task_id="derdelus") ==
In lumea oilor Dubota se afla pe un deal triunghiular cu N niveluri, de forma urmatoare.
*
* *
* * *
* * * *
Astfel, Dubota poate sa coboare pe la stanga sau la dreapta. La fiecare pas el poate sa coboare unul, pana la M niveluri. De asemenea pot exista locatii in care cresc flori, locatii in care oaia nu se poate opri (pentru a nu distruge florile) dar peste care poate totusi sa sara. Dubota sare tot timpul intr-o linie dreapta in stanga sau in dreapta, de exemplu, din 1,1 poate sa sara in stanga un nivel in 2,1, 2 niveluri in 3,1..., sau in dreapta un nivel in 2,2, 2 niveluri 3,3 samd. Dubota nu poate sa sara pe un nivel mai mare sau egal decat cel pe care se afla la un moment dat, salturile le face la vale.
Dubota se afla in locatia (i, j) atunci el poate sari la stanga in (k, j) sau la dreapta (k, j + k - i) unde k > i.
Sa se afiseze in cate feluri poate cobora Dubota pornind din varful dealului si terminand in fiecare din locatiile de la baza dealului. (Se afiseaza N valori modulo 666013)
Oile se antrenează pentru a sări peste garduri în visele oamenilor. Ele îşi exerseaza aterizările pentru că unii oameni au nişte garduri complicate prin vise: unele înalte, altele late, şi unii chiar ziduri comparabile cu Marele Zid Chinezesc, ba chiar pot să fie şi împrejmuite de şanţuri umplute cu apă şi în care sălăşluiesc crocodili. Oile trebuie să fie foarte bine antrenate pentru a face faţă viselor acestora.
În lumea oilor ele au un complex întreg pentru perfecţionarea săriturilor, iar pe noi ne interesează o piramidă. Oile se urcă în vârful acesteia şi încep să coboare pe una din faţade. De alungul coborârii ele pot să rămâna numai pe acea faţadă. Piramida are la bază $N$ cuburi, pe nivelul superior $N-1$ şi aşa mai departe până în vârf unde este un sigur cub de pe care oile îşi încep antrenamentul. De pe acest cub ele pot să sară pe cubul din stânga sau pe cel din dreapta. Piramida aceasta este însă destul de veche şi cu timpul $P$ cuburi s-au deteriorat şi nu mai este sigur să se aterizeze pe ele.
*
* *
* # *
* * * *
Oaia Dubota se pregăteşte să îşi înceapă antrenamentul. Ea se află în vârful piramidei şi analizează faţada pe care să coboare. Dubota este o oaie destul de şmecheră, şi deşi oile începătoare pot să sară doar pe nivelul inferior al piramidei fără a se răni, Dubota poate să sară la un pas între $1$ şi $M$ niveluri. Aşa că dacă se află în locaţia $(i, j)$ atunci ea poate sări la stânga in $(k, j)$ sau la dreapta $(k, j + k - i)$ unde $i < k$ si $k - i ≤ M$.
Dubota este interesată să ştie în câte feluri poate coborî până pe cuburile de pe primul nivel. Problema ei este ca s-a încurcat încercând să calculeze şi vă cere ajutorul.
Să se afişeze în câte feluri poate coborî Dubota pornind din vârful dealului şi terminând în fiecare din locaţiile de la baza dealului. Deoarece valorile pot fi foarte mari, să se afişeze acestea modulo $666013$.
h2. Date de intrare
Fişierul de intrare $derdelus.in$ ...
Fişierul de intrare $derdelus.in$ va conţine pe prima linie valorile $N$, $M$ şi $P$. Pe următoarele $P$ linii se vor găsi cuburile care sunt deteriorate sub forma nivel şi indice. Nivelurile sunt numerotate de sus în jos începând cu $1$ şi terminând cu $N$ şi pe un nivel cuburile sunt numerotate de la stânga la dreapta.
h2. Date de ieşire
În fişierul de ieşire $derdelus.out$ ...
În fişierul de ieşire $derdelus.out$ trebuie să afişaţi $N$ valori modulo $666013$ reprezentând numărul de posibilităţi pe care le are Dubota de a ajunge pe fiecare din cuburile de pe nivelul de la baza piramidei.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 1000$
* $1 ≤ M ≤ N$
* $0 ≤ P ≤ N * (N + 1) / 2$
* Pozitia de start (1, 1) nu poate fi stricata.
h2. Exemplu
table(example). |_. derdelus.in |_. derdelus.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 2 2
3 2
2 2
| 3 2 2 1
|
h3. Explicaţie
...
*
* #
* # *
* * * *
Pentru prima casuta, cele trei posibilitati sunt: $(1, 1) -> (3, 1) -> (4, 1); (1, 1) -> (2, 1) -> (4, 1); (1, 1) -> (2, 1) -> (3, 1) -> (4, 1)$.
Pentru casuta a doua: $(1, 1) -> (3, 1) -> (4, 2); (1, 1) -> (2, 1) -> (3, 1) -> (4, 2)$.
Pentru a treia casuta: $(1, 1) -> (2, 1) -> (4, 3); (1, 1) -> (3, 3) -> (4, 3)$.
Pentru casuta a patra: $(1, 1) -> (3, 3) -> (4, 4)$.
== include(page="template/taskfooter" task_id="derdelus") ==
