Home

Contest: Task: Related: TaskC TaskE

Score : $400$ points

Problem Statement

Given is an integer $S$. Find how many sequences there are whose terms are all integers greater than or equal to $3$, and whose sum is equal to $S$. The answer can be very large, so output it modulo $10^9 + 7$.

Constraints

  • $1 \leq S \leq 2000$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$S$

Output

Print the answer.

Sample Input 1

7

Sample Output 1

3

$3$ sequences satisfy the condition: $\{3,4\}$, $\{4,3\}$ and $\{7\}$.

Sample Input 2

2

Sample Output 2

0

There are no sequences that satisfy the condition.

Sample Input 3

1729

Sample Output 3

294867501