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

Poveste si cerinta...

O piramida de inaltime $n$ are la baza (baza fiind considerata de nivel $1$) $n$ numere naturale nenule, pe nivelul urmator al piramidei (nivelul $2$) exista $n-1$ numere, fiecare numar de pe nivelul $2$ fiind obtinut cu formula $P2,i$=$P1,i$+$P1,i+1$ pentru $i$=$1$,…,$n-1$ si asa mai departe, pe nivelul $k$ fiind $n-k+1$ numere, fiecare numar de pe acest nivel fiind obtinut cu formula $Pk,i$=$Pk-1,i$+$Pk-1,i+1$ pentru $i$=$1$,…,$n-k+1$.
 
Piramida este $S-generatoare$ daca numarul de pe ultimul nivel este $S$.
 
h2. Cerinta
 
Pentru o valoare $S$ data, se cere sa se determine cate piramide $S-generatoare$ de inaltime maxima exista.
De exemplu, pentru $S$=$10$, exista $3$ astfel de piramide !problema/piramida?pir1.jpg!
 
Piramidele !problema/piramida?pir2.jpg! sunt $10-generatoare$, dar nu au inaltime maxima.

h2. Date de intrare

Fisierul de intrare $piramida.in$ ...

In fisierul $piramida.in$ se afla un singur numar natural reprezentand valoarea lui $S$.

h2. Date de iesire

In fisierul de iesire $piramida.out$ ...

Fisierul de iesire $piramida.out$ va contine o singura linie pe care va fi scris un singur numar natural reprezentand numarul total de piramide $S generatoare$ de inaltime maxima modulo $10000$.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ S ≤ 600000$

h2. Exemplu
table(example). |_. piramida.in |_. piramida.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 1
| 1
|
| 3
| 2
|
| 10
| 3
|
| 20
| 7

|

| 101
| 714
|

h3. Explicatie
...

== include(page="template/taskfooter" task_id="piramida") ==