AOJ考试版's OJ 竞赛&作业 状态 竞赛&作业问题列表
登录 注册

安徽科技工程大学程序设计在线考试系统Ver3.0

诚信考试，杜绝作弊！

问题 H: 骨牌覆盖

内存限制：512 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较
上一题返回比赛提交提交记录 下一题

题目描述

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

输入格式

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

输出格式

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

输入样例 复制 

3

输出样例 复制 

2

数据范围与提示

递推，动态规划