Problem H: 骨牌覆盖

上一题 正确率: $38.32\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1177$ 正确数量 $451$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 递归

Description

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

Input

n
40%  数据 n<=20
80% 数据 n<=100
100%的数据 n<=20000

Output

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

Sample Input复制

3

Sample Output复制

2

提示

递推，动态规划