Cerință

Se dă un număr natural $K$. Aflați al $K$-lea termen al șirului Fibonacci modulo $10^9 + 7$.

Date de intrare

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

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

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

Exemplul 1

kfib.in

6

kfib.out

8

Explicație

Primii $10$ termeni ai șirului Fibonacci sunt:

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

Al $6$-lea termen fiind $8$.

Exemplul 2

kfib.in

123456789

kfib.out

62791945