Fibonacci Sequence 3

Problem Description

The Fibonacci sequence is the following sequence: $1, 1, 2, 3, 5, 8, \dots$. Starting from the third number, each number is the sum of the previous two.

Compute the sum of the first $n$ terms of this sequence, modulo $10^9 + 7$.

Input Format

The first line contains an integer $n$.

Output Format

Output one integer — the answer.

Sample Input

5

Sample Output

12

Constraints

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