O piramidă de înălţime n are la bază (baza fiind considerată de nivel 1) n numere naturale nenule, pe nivelul următor al piramidei (nivelul 2) există n-1 numere, fiecare număr de pe nivelul 2 fiind obţinut cu formula P2,i=P1,i+P1,i+1 pentru i=1,…,n-1 şi aşa mai departe, pe nivelul k fiind n-k+1 numere, fiecare număr de pe acest nivel fiind obţinut cu formula Pk,i=Pk-1,i+Pk-1,i+1 pentru i=1,…,n-k+1.
Piramida este S-generatoare dacă numărul de pe ultimul nivel este S.

Cerinţă

Pentru o valoare S dată, se cere să se determine câte piramide S-generatoare de înălţime maximă există.
De exemplu, pentru S=10, există 3 astfel de piramide



Piramidele:



sunt 10-generatoare, dar nu au înălţime maximă.

Date de intrare

În fişierul piramida1.in se află un singur număr natural reprezentând valoarea lui S.

Date de ieşire

Fişierul de ieşire piramida1.out va conţine o singură linie pe care va fi scris un singur număr natural reprezentând numărul total de piramide S-generatoare de înălţime maximă modulo 10000.

Restricţii

0 < S < 600 000

Exemple

piramida1.in	piramida1.out
10	3
20	7
101	714

autor: Prof. Rodica Pintea

propunător: Prof. Emanuela Cerchez

Liceul de Informatica ″Grigore Moisil″

emanuela.cerchez@gmail.com