时间限制：1秒　　内存限制：256M

---

【题目描述】

　　有 1 行 \(N\) 列的长方形，用 \(1×1\)、 \(1×2\)、 \(1×3\) 的骨牌铺满方格，请计算有多少种不同的铺法。

　　例如n=3时，共有如下四种铺法。

【输入格式】

　　一个整数 \(N\)，表示长方形的列数。

【输出格式】

　　输出一个整数，表示方案总数，这个数可能很大，所以只需输出模 \(10007\) 后的结果。

【输入输出样例1】

　Input

3

　Output

4

【输入输出样例2】

　Input

50

　Output

7081

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤1000\)。

【来源】

　　Mr.he