== include(page="template/taskheader" task_id="margiki") ==
Poveste şi cerinţă...
Margiki, afectat de perioada actuala, s-a facut putin mai grasut. Stiind ca toate salile de forta sunt inchise, acesta ii cere cateva idei lui Norocel din tinutul *iGorj*. Norocel are un palat imens cu *$N$* trepte (e greu sa ai atatea etaje + mansarda). Acesta il invita pe Margiki sa urce toate cele *$N$* scari si ii garanteaza ca va da jos kilogramele nedorite. Margiki poate urca scarile in *$3$* moduri: sa sara cu piciorul stang cate o treapta, sa sara cu piciorul drept doua trepte sau sa sara direct $3$ trepte, luandu-si avant cu ambele picioare. Norocel i-a promis lui Margiki ca il va rasplati cu o sticla de apa daca atunci cand va ajunge la treapta cu numarul *$N$*, ii va spune si in *cate moduri distincte* ar fi putut urca toate aceste trepte (suntem siguri ca Margiki va reusi sa urce trepele in orice situatie). Pentru ca raspunsul este unul foarte mare, Norocel vrea sa afle doar *modulo $1 000 000 007$* (restul impartirii la acest numar).
h2. Date de intrare
Fişierul de intrare $margiki.in$ ...
Fişierul de intrare $margiki.in$ contine pe prima linie un singur numar $N$, reprezentand numarul de trepte.
h2. Date de ieşire
În fişierul de ieşire $margiki.out$ ...
În fişierul de ieşire $margiki.out$ se va afla pe prima linie un singur numar reprezentand numarul total de moduri distincte de a urca cele $N$ trepte.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 10^12^$
* Pentru 20 de puncte, $1 ≤ N ≤ 15$
* Pentru alte 20 de puncte, $1 ≤ N ≤ 10^5^$
* Pentru alte 20 de puncte, $1 ≤ N ≤ 10^7^$
* **Atenţie la limita de memorie!**
* *Comisia va ureaza Sarbatori Fericite anticipat!*
h2. Exemplu
table(example). |_. margiki.in |_. margiki.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3
| 4
|
| 96400
| 129153773
|
h3. Explicaţie
...
In primul exemplu, Margiki poate: sa sara o treapta cu piciorul stang, apoi 2 trepte cu piciorul drept SAU sa sara 2 trepte cu piciorul drept, apoi o treapta cu piciorul stang SAU sa sara direct toate cele 3 trepte luandu-si avant cu ambele picioare SAU sa sara de 3 ori cate o treapta cu piciorul stang
== include(page="template/taskfooter" task_id="margiki") ==
