Laiko ribojimas: 1s

Atminties ribojimas: 128MB

Duomenų failas: fibonacci.in

Rezultatų failas: fibonacci.out

Jei norite pateikti savo sprendimą - prisijunkite.

Fibonačio skaičiai

Skaičių seka 1,1,2,3,5,8,13,21,... vadinama Fibonačio seka. Ši seka visada prasideda dviem vienetais, o visi likę elementai yra lygūs dviejų prieš tai buvusių elementų sumai. Tiksliau šnekant, skaičių seka F vadinama Fibonačio seka, jei:

  • F_1=F_2=1
  • F_n=F_{n-1}+F_{n-2},n>3
Parašykite programą, apskaičiuojančią n-ojo Fibonačio sekos nario reikšmę moduliu 10^9+7.

Pradiniai duomenys

Pirmoje ir vienintelėje eilutėje įvestas vienas natūralusis skaičius n (1\\leqn\\leq10^18).

Rezultatai

Programa turi išvesti vieną skaičių - n-ąjį Fibonačio sekos skaičių (F_n) moduliu 10^9+7.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
2
 
1
 
4
 
3
 
15
 
610