题目描述

用红色的1×1和黑色的2×2两种规格的瓷砖不重叠地铺满n*3的路面，求出有多少种不同的铺设方案。

输入

一个整数n，0<n<1000。

输出

一个整数，为铺设方案的数量mod 10007的结果。

样例输入 Copy

2

样例输出 Copy

3