题目描述

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

3

样例输出 #1

5

提示

【样例​说明】

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