Keďže výťah nechodí, Rišo každý deň chodí po schodoch. Aby to preňho nebola nuda, začal striedať kroky, pri ktorých ide na ďalší schod, s krokmi, keď jeden schod preskočí.
Teraz ho zaujíma, koľkými rôznymi spôsobmi dokáže prejsť celé schodisko, ak môže pri každom kroku spraviť buď jeden alebo dva schody naraz.
Skúste odpovedať na otázku: koľkými spôsobmi sa viem dostať na schod $i$?
Na jedinom riadku vstupu nájdete číslo $n$ -- počet schodov na Rišovom schodisku.
Na jediný riadok výstupu vypíšte jedno číslo -- počet spôsobov, ktorými môže Rišo prejsť po schodoch. Keďže toto číslo môže byť naozaj veľké, vypíšte ho ako zvyšok po delení $10^9+7$.
5
8
123
116969271