题目描述

       朱老师对现在一个月0.3w的工资很不满意，于是准备外出兼职去搬砖。朱老师到达工厂，包工头对朱老师说：你面前有n块板砖，需要你把这n块板砖搬到指定的地点。因为朱老师的体力有限 ，每次最多只能搬动3块板砖。

       麻烦你帮小朱老师算一下，小朱老师有多少种办法可以将n块板砖搬到指定地点。

输入

第一行包含一个正整数n，表示有n块板砖。

输出

有多少种办法可以将n块板砖搬到指定地点。这个数可能很大，结果对100007取模。

Samples

3

4

数据范围

对于40％的数据１＜＝ｎ＜＝１0．

对于１00％的数据　１＜＝ｎ＜＝500，