101783: [AtCoder]ABC178 D - Redistribution
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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