3135: 四铺地砖
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
有一条道路需要铺设地砖，这条道路由 �×2n×2 个方格组成。存在两种规格的地砖，一种是 1×21×2 规格的，也就是恰好可以覆盖两个方格，另一种是 2×22×2 规格的。两种规格的砖头的数量没有限制。请计算有多少种方法，将这条道路铺满地砖。
由于方案数可能很大，输出它模 1,000,000,0071,000,000,007 的余数即可。
输入
单个整数：表示 �n。
- 对于 30%30% 的数据，1≤�≤151≤n≤15；
- 对于 70%70% 的数据，1≤�≤500001≤n≤50000；
- 对于 100%100% 的数据，1≤�≤1000001≤n≤100000。
输出
单个整数：表示方案数模 1,000,000,0071,000,000,007 的余数。
样例输入 复制
2样例输出 复制
3提示
171