题目描述

​ 给你一个整数$N$,问有多少种不同的序列$A$,满足$A_i>=3$,且$\sum_{i=1}^kA_i = N$.

输入格式

第一行，一个大于等于$3$的整数$N$.

输出格式

一个整数,表示序列的个数,如果个数过大,答案对于$10^9 + 7$取模.

样例数据

输入1

3

输出1

1

输入2

1729

输出2

294867501

数据范围

对于 $30\%$ 的数据：$n<=30$。

对于$70\%$的数据: $n\le 1000$

对于 $100\%$ 的数据：$n \le 10^6$。