S1 - Schody 1

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Úloha

Hore a dole, behala Olívia celý deň po schodoch. Treba si predsa udržiavať kondičku. A beh po schodoch je na to ako stvorený. Schody v pevnosti UVZ sú dosť veľké a majú presne N schodíkov. A Olívia vždy vybehne až na samý vrch. Naviac vie vždy stúpiť len na schod o jedna alebo o dva vyššie. A aby sa nenudila, zakaždým to spraví iným spôsobom. Zistite koľkokrát dnes Olívia vybehla po schodoch a toto číslo vypíšte modulo 1000007.

Dve vybehnutia pokladáme za rôzne, ak po ich zapísaní ako postupnosť 1 a 2, sa tieto dve postupnosti líšia aspoň na jednom mieste.

Vstup

Vstup obsahuje jeden riadok obsahujúci jedno celé číslo, počet schodov N.

S1

1 ≤ N ≤ 10⁶

S2

1 ≤ N ≤ 10¹⁸

Výstup

Výstup obsahuje jediný riadok s počtom navzájom rôznych postupností podľa zadania.

Príklad

Vstup:

Výstup:

Možnosti:

1,1,1,1
1,1,2
1,2,1
2,1,1
2,2

21 Finále