Description

As we all know, the Fibonacci sequence is defined by the following properties:

$$F_n = \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.$$

Please compute the value of $F_n \bmod 10^9 + 7$.

Input Format

A single line containing a positive integer $n$.

Output Format

Output a single integer on one line representing the answer.

5

5

10

55

Hint

Constraints
For 60% of the testdata, $1 \le n \le 92$.
For 100% of the testdata, $1 \le n < 2^{63}$.

Translated by ChatGPT 5