== 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