问题描述

假设你很喜欢吃零食。将今天定义为第1天，你决定从今天开始连续 $N$ 天考虑如何吃零食。为此，你设定了以下规则：

• 每天早上、中午和晚上各吃一次零食。
• 每次吃零食只能选择“曲奇饼干”、“巧克力”或“蛋糕”中的一种。
• 不可以连续两次吃同一种零食。（这个规则也适用于第$i$天晚上和$(i+1)$天早上。）
• 早上吃零食时只能选择“曲奇饼干”或“巧克力”。

对于这 $3N$ 次吃零食的情况，计算满足以上规则的吃法有多少种，结果对 $10^9+7$ 取模。

注意，第1天早上可以选择吃“曲奇饼干”或“巧克力”，并且假设你手头有足够多的三种零食。

约束条件

• $1\\le N\\le 10^{18}$
• $N$ 为整数

部分点

本问题分为若干部分得分。

• 对于满足 $N \\leq 10^5$ 的输入数据作出正确回答，可得 300 分。

输入

从标准输入读入数据。

$N$

输出

输出答案。

输入示例 1

1

输出示例 1

8

将“曲奇饼干”表示为“曲”，“蛋糕”表示为“蛋”，“巧克力”表示为“巧”，则共有以下8种可能：

(早上、中午、晚上) \= (曲、蛋、曲), (曲、蛋、巧), (曲、巧、曲), (曲、巧、蛋), (巧、蛋、曲), (巧、蛋、巧), (巧、曲、蛋), (巧、曲、巧)

请注意不能连续吃同一种零食以及早上不吃蛋糕。

输入示例 2

2

输出示例 2

40

请注意不能连续吃相同的零食，这也适用于第一天晚上和第二天早上。

输入示例 3

100000

输出示例 3

607318103