Problem Description

As everyone knows, the Fibonacci sequence is a series that satisfies 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 representing the answer.

Sample Input and Output

Sample Input #1

5

Sample Output #1

5

Sample Input #2

10

Sample Output #2

55

Notes

[Data Range]
For 60% of the data, $1\le n \le 92$;
For 100% of the data, $1\le n < 2^{63}$.

见题面 Input 部分

见题面 Output 部分