问题描述

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

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

输入格式

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

输出格式

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

样例输入输出

3

5

样例说明

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

评测用例规模与规定

对于所有的评测样例,$1 \leqslant N \leqslant 10000000$。

运行限制

• 最大运行时间：$3s$
• 最大运行内存：$512M$