题目描述

蜂巢由一些正六边形的格子组成，这些格子分上下两排，一共有 $n$ 个格子。如果 $n$ 是偶数，则每一排分别有 $n/2$ 个格子，若 $n$ 是奇数，则下排比上排多一个。

一只成年的蜜蜂，会占据两个相邻的格子，而一只蜜蜂的幼虫只能占据一个格子。

若蜂巢所有的格子都被蜜蜂或幼虫占据了，那么会有多少种不同的方案呢？两个方案若在任何一个格子上的布置有区别，就被看作是不同的方案。

答案可能很大，输出模 $1,000,000,007$ 的余数。

输入格式

• 单个整数：表示 $n$

输出格式

• 单个整数：表示答案。

4

8

数据范围

• $30\%$ 的数据，$1\leq n\leq 10$
• $60\%$ 的数据，$1\leq n\leq 1,000$
• $100\%$ 的数据，$1\leq n\leq 1,000,000$