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

This comment is hidden due to too much negative feedback. Click here to view it.

This comment is hidden due to too much negative feedback. Click here to view it.