D - Redistribution Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

整数 S が与えられます。 すべての項が 3 以上の整数で、その総和が S であるような数列がいくつあるか求めてください。ただし、答えは非常に大きくなる可能性があるので、 10^9+7 で割った余りを出力してください。

制約

  • 1 \leq S \leq 2000
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

S

出力

答えを出力せよ。

入力例 1

7

出力例 1

3

数列 \{3,4\},\{4,3\},\{7\} の 3 つが条件を満たします。

入力例 2

2

出力例 2

0

条件を満たす数列は存在しません。

入力例 3

1729

出力例 3

294867501

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