B. 积木画

传统题

2000ms

512MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

小明最近迷上了积木画, 有这么两种类型的积木, 分别为 $I$ 型（大小为 2 个单位面积) 和 $L$ 型 (大小为 3 个单位面积):

同时, 小明有一块面积大小为 $2 \times N$ 的画布, 画布由 $2 \times N$ 个 $1 \times 1$ 区域构成。小明需要用以上两种积木将画布拼满, 他想知道总共有多少种不同的方式? 积木可以任意旋转, 且画布的方向固定。

输入一个整数 $N$ ，表示画布大小。

输出一个整数表示答案。由于答案可能很大，所以输出其对 $1000000007$ 取模后的值。

五种情况如下图所示，颜色只是为了标识不同的积木：

对于所有测试用例， $1 ≤ N ≤ 10000000$ .