For each integer $N$, a good array is a non-empty array which satisfies the following conditions:

1. Every element in the array is between the array's size and $N$, inclusive.
2. The array is strictly increasing.
3. There are no two consecutive integers in the array.

Given an integer $N$, determine the number of good arrays.

Constraints

$1\le N\le {10}^6$

Subtask 1 [10%]

$1\le N\le 10$

Subtask 2 [10%]

$1\le N\le {10}^3$

Subtask 3 [80%]

No additional constraints.

Input Specification

The only line contains an integer, $N$.

Output Specification

Output the number of good arrays modulo ${10}^9+7$.

Sample Input

4

Sample Output

5

Explanation for Sample

The good arrays are

• $\{1\}$
• $\{2\}$
• $\{3\}$
• $\{4\}$
• $\{2,4\}$

Every array is strictly increasing, has elements between the array size and $N$, and contains no consecutive integers ($x,x+1$).