derdelus

Derdelus

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

Oile se antreneaza pentru a sari peste garduri in visele oamenilor. Ele isi exerseaza aterizarile pentru ca unii oameni au niste garduri complicate prin vise: unele inalte, altele late, si unii chiar ziduri comparabile cu Marele Zid Chinezesc, ba chiar pot sa fie si imprejmuite de santuri umplute cu apa si in care salasluiesc crocodili. Oile trebuie sa fie foarte bine antrenate pentru a face fata viselor acestora.

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.

In lumea oilor ele au un complex intreg pentru perfectionarea sariturilor, iar pe noi ne intereseaza o piramida. Oile se urca in varful acesteia si incep sa coboare pe una din fatade. De alungul coborarii ele pot sa ramana numai pe acea fatada. Piramida are a baza N cuburi, pe nivelul superior N-1 si asa mai departe pana in varf unde este un sigur cub de pe care oile isi incep antrenamentul. De pe acest cub ele pot sa sara pe cubul din stanga sau pe cel din dreapta. Piramida aceasta este insa destul de veche si cu timpul P cuburi s-au deteriorat si nu mai este sigur sa se aterizeze pe ele.

Î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 pregateste sa isi inceapa antrenamentul. Ea se afla in varful piramidei si analizeaza fatada pe care sa coboare. Dubota este o oaie destul de smechera, si desi oile incepatoare pot sa sara doar pe nivelul inferior al piramidei fara a se rani, Dubota poate sa sara la un pas intre 1 si M niveluri. Asa ca daca se afla in locatia (i, j) atunci ea poate sari la stanga in (k, j) sau la dreapta (k, j + k - i) unde k > i.

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 interesata sa stie in cate feluri poate cobora pana pe cuburile de pe primul nivel. Problema ei este ca s-a incurcat incercand sa calculeze si va cere ajutorul.

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.

Sa se afiseze in cate feluri poate cobora Dubota pornind din varful dealului si terminand in fiecare din locatiile de la baza dealului. Deoarece valorile pot fi foarte mari, sa se afiseze acestea modulo 666013.

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$ va contine pe prima linie valorile N, M si P. Pe urmatoarele P linii se vor gasi cuburile care sunt deteriorate sub forma nivel si indice. Nivelurile sunt numerotate de sus in jos incepand cu 1 si terminand cu N si pe un nivel cuburile sunt numerotate de la stanga la dreapta.

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$ trebuie sa afisati N valori modulo 666013 reprezentand numarul de posibilitati pe care il are Dubota de a ajunge pe fiecare din cuburile de pe nivelul de la baza piramidei.

Î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$
 

* $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") ==

5306