Kfib

Time limit: 0.05s
Memory limit: 64MB
Input: kfib.in
Output: kfib.out

Cerință

Se dă un număr natural KK. Aflați al KK-lea termen al șirului Fibonacci modulo 109+710^9 + 7.

Date de intrare

Pe prima linie a fișierului de intrare kfib.in se află numărul natural KK.

Date de ieșire

Pe prima linie a fișierului de ieșire kfib.out se va afla răspunsul la cerință.

Restricții și precizări

  • 1K10181 \leq K \leq 10^{18}

Exemplul 1

kfib.in

6

kfib.out

8

Explicație

Primii 1010 termeni ai șirului Fibonacci sunt:

1,1,2,3,5,8,13,21,34,551, 1, 2, 3, 5, 8, 13, 21, 34, 55

Al 66-lea termen fiind 88.

Exemplul 2

kfib.in

123456789

kfib.out

62791945

Problem info

ID: 1010

Editor: LucaLucaM

Source: Folclor

Tags:

Log in or sign up to be able to send submissions!