You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

哀牢山的七彩梯田

题目背景

在红河州元阳县的哀牢山深处，哈尼族人民开垦出了举世闻名的哈尼梯田。每当春耕时节，层层叠叠的梯田倒映着蓝天白云与霞光，呈现出缤纷的色彩。

哈尼族的祭司“咪谷”计划在祭祀大典上，沿着山脊的 $N$ 块梯田布置装饰。

题目描述

每一块梯田可以呈现出三种颜色：

1. 霞光红（代码 1）
2. 水天蓝（代码 2）
3. 稻穗金（代码 3）

为了遵循自然万物相生相克的规律，梯田的颜色布置必须满足以下严苛的古训：

• 红火不相见：由于红色象征烈火，为了防止干旱，相邻的两块梯田不能同时涂成“霞光红”（即序列中不能出现连续的 1）。
• 金石不相撞：由于金色象征成熟的谷物，需要避开生硬的金属色，相邻的两块梯田不能同时涂成“稻穗金”（即序列中不能出现连续的 3）。
• 水天一色：“水天蓝”象征生命之源，它性格温和，可以与任何颜色（包括它自己）相邻。

由于梯田延绵不绝，$N$ 的数值极广。请你计算出，在满足古训的前提下，布置这 $N$ 块梯田共有多少种颜色组合方案？

由于方案数可能是一个天文数字，请输出结果对 $10^9 + 7$ 取模后的值。

输入格式

输入仅包含一个正整数 $N$，表示梯田的总数。

输出格式

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

样例 #1

样例输入 #1

2

样例输出 #1

7

样例 #2

样例输入 #2

10

样例输出 #2

8119

数据范围与提示

• 对于 $20\%$ 的数据：$1 \le N \le 20$。
• 对于 $40\%$ 的数据：$1 \le N \le 10^6$。
• 对于 $100\%$ 的数据：$1 \le N \le 10^{18}$。

提示：

1. 当 $N=2$ 时，方案有：(1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2)。总共 7 种。