Fibonacci Sequence 2

Problem Description

The Fibonacci sequence is the sequence $1, 1, 2, 3, 5, 8, \dots$, in which every term starting from the third is the sum of the two preceding terms.

Compute the $n$-th term of this sequence modulo $10^9 + 7$.

Input Format

The first line contains an integer $n$.

Output Format

Output one line containing a single integer: the answer.

Sample Input

5

Sample Output

5

Constraints

For $100\%$ of the test cases, $1 \le n \le 10^9$.