1426: 骨牌覆盖

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：1 Solved：1

Description

用一个1*3的骨牌去覆盖一个3*n的长方形，求所有可能的方案数,n的范围（n的范围 1<=n<=10000）方案数请输出对1000000007取模的结果

Input

n

40%  数据 n<=200

80% 数据 n<=1000

100%的数据 n<=10000

Output

所有可能方案数 对1000000007取模的结果

Sample Input Copy 

3

Sample Output Copy 

2

HINT

递推，动态规划