quantum is not feeling well today, and has decided to create a more painful version of the simple Fibonacci problem.

Recall that the Fibonacci sequence is a well known sequence of numbers in which

$$\displaystyle F(n) = \begin{cases} 0, & \text{if } n = 0 \\ 1, & \text{if } n = 1 \\ F(n-2) + F(n-1), & \text{if } n \ge 2 \end{cases}$$

You are given a number ~N~ ~(1 \le N \le 10^{100\,000})~, find the ~N^{th}~ Fibonacci number, modulo ~1\,000\,000\,007~ ~(= 10^9 + 7)~.

#### Input Specification

The first line of input will have the number ~N~.

#### Output Specification

The ~N^{th}~ Fibonacci number, modulo ~1\,000\,000\,007~ ~(= 10^9 + 7)~.

#### Sample Input

`26`

#### Sample Output

`121393`

## Comments

What's different about this problem to the simpler one?

The highest possible value for

can be greater than the one in the simpler version. There is also a lower time limit.Where can I find a Python 3 explanation for this problem?

Where can I find editorial with explanation for this problem?

solution is this

Thank you, but I got AC already. I was confused about the Pisano period, but that's not required in this question. Store n in string and use matrix exponentiation properly :)

A hint is : if you know the answer for n=500 in matrix X, u can get an answer for n=5000 by X^(10) :)

https://usaco.guide/plat/mat-exp?lang=cpp

study PISANO number for fibonacci numbers and also solve https://www.spoj.com/problems/PISANO/cstart=10

Last topic might help!!

This comment is hidden due to too much negative feedback. Show it anyway.

Use math.