* # *
 * * * *

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

  * # *
 * * * *

Pentru prima casuta, cele patru posibilitati sunt: $(1, 1) -> (3, 1) -> (4, 1); (1, 1) -> (2, 1) -> (4, 1); (1, 1) -> (2, 1) -> (3, 1) -> (4, 1)$.

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

5306