A Math Contest P5 - Good Arrays

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

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.


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


Sample Output


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


There are no comments at the moment.