(23-24赛季)稠州常规赛15
P3. 蜜蜂与幼虫
描述
蜂巢由一些正六边形的格子组成，这些格子分上下两排，一共有 n 个格子。如果 n 是偶数，则每一排分别有
n/2 个格子，若 n 是奇数，则下排比上排多一个。
一只成年的蜜蜂，会占据两个相邻的格子，而一只蜜蜂的幼虫只能占据一个格子。
若蜂巢所有的格子都被蜜蜂或幼虫占据了，那么会有多少种不同的方案呢？两个方案若在任何一个格子上的布置有区别，就被看作是不同的方案。
答案可能很大，输出模 1,000,000,007 的余数。
输入
单个整数：表示 n
输出
单个整数：表示答案。
样例
输入
4
输出
8
提示
30% 的数据，1≤n≤10
60% 的数据，1≤n≤1,000
100% 的数据，1≤n≤1,000,000
提交
题目参数
| 时间限制 | 1 秒 |
| 内存限制 | 128 MB |