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

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

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

h2. Restricţii

* $1 ≤ N ≤ 10^12$

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

* 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