在一个狭长的双排防御阵地中，布置了两排紧密相连的菱形防御格，总共有 n 个防御格。如果 n 是偶数，则上下两排各有 n/2 个防御格；如果 n 是奇数，则下排比上排多一个防御格。防御格的排列方式如下图所示（上下两排交错对齐）：

当两个防御格有公共的边或公共的顶点时，我们认为连个防御格相邻，比如上图中从左向右数第 1 个防御格和第 2 个、第 3 个防御格都是相邻的。

在塔防作战中，一个重型防御塔需要占据两个相邻的防御格来稳定部署，而一个轻型防御塔只能占据一个防御格。

现在要求用重型防御塔和轻型防御塔将所有防御格完全覆盖（每个防御格恰好被占据一次，不重叠、不留空），以构建完整的防线。请问共有多少种不同的部署方案？两种方案只要在任意一个防御格上的部署方式不同，就视为不同方案。

答案可能很大，请输出方案数对 10^9 + 7 取模后的结果。

第一行包含一个正整数 n，表示防御格的总数。

输出一行一个非负整数，表示方案数对 10^9 + 7 取模后的结果。

数据范围

• 对于 30\% 的数据，满足 1 \le n \le 10；
• 对于 60\% 的数据，满足 1 \le n \le 1000；
• 对于 100\% 的数据，满足 1 \le n \le 10^6。

月赛递推动态规划26年5月