P10685: 铺地砖
传统题
1.000s
时间限制
128MB
内存限制
2 提交
1 解决
【题目描述】
【题目描述】
有一条道路需要铺设地砖，这条道路由n×3个方格组成。只有一种规格的地砖，大小是 1×2 规格的，也就是恰好可以覆盖两个方格。请计算有多少种方法，将这条道路铺满地砖。
由于方案数可能很大，输出它模 1,000,000,007 的余数即可。
【输入格式】
单个整数：表示n。(保证n为偶数)
【输出格式】
单个整数：表示方案数模1,000,000,007 的余数。
【数据范围】
对于30%的数据，1≤n≤16；
对于70%的数据，1≤n≤300；
对于100%的数据，1≤n≤200000。
【输入样例一】
2
【输出样例一】
3
【输入样例二】
8
【输出样例二】
153
【输入】
单个整数：表示n。(保证n为偶数) 【输出】
单个整数：表示方案数模1,000,000,007 的余数。