Integer Partition

A positive integer n can be represented as the sum of several positive integers: n = n₁ + n₂ + … + n_k, where n₁ ≥ n₂ ≥ … ≥ n_k, k ≥ 1.

Such a representation is called a partition of the positive integer n.

Given a positive integer n, find the total number of different partitions of n.

Input Format

One line containing an integer n.

Output Format

One line containing an integer representing the total number of partitions.

Since the answer may be very large, output the result modulo 10⁹ + 7.

Constraints

1 ≤ n ≤ 1000

Sample Input

5

Sample Output

7