Kfib

Task

Given a natural number $K$, find the $K^{th}$ term of the Fibonacci sequence, modulo $10^9 + 7$.

Input data

The first line of the file kfib.in contains the natural number $K$.

Output data

The first line of the file kfib.out will contain the answer to this task.

Constraints and clarifications

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

Example 1

kfib.in

6

kfib.out

8

Explanation

The first $10$ terms of the Fibonacci sequence are:

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

The $6^{th}$ term is $8$.

Example 2

kfib.in

123456789

kfib.out

62791945