Kfib

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

Task

Given a natural number KK, find the KthK^{th} term of the Fibonacci sequence, modulo 109+710^9 + 7.

Input data

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

Output data

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

Constraints and clarifications

  • 1≤K≤10181 \leq K \leq 10^{18}

Example 1

kfib.in

6

kfib.out

8

Explanation

The first 1010 terms of the Fibonacci sequence are:

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

The 6th6^{th} term is 88.

Example 2

kfib.in

123456789

kfib.out

62791945

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