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.

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

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

| 4 3 2

| 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