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

---

【题目描述】

　　有 3 行 \(N\) 列的长方形，可以用 \(N\) 个 \(1×3\) 的骨牌铺满，但可能有很多种不同的铺法。

　　现在给出自然数 \(N\)，请回答当长方形为 \(3\) 行 \(N\) 列时，有多少种不同的铺设方法。

【输入格式】

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

【输出格式】

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

【输入输出样例1】

　Input

2

　Output

1

【输入输出样例2】

　Input

4

　Output

3

【输入输出样例3】

　Input

10

　Output

28

【数据限制】

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

【来源】

　　Mr.he