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