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~).