AT_cpsco2019_s1_d.Dessert Planning

やむなく君非常喜欢吃零食。从今天（第 $1$ 天）开始，他打算在接下来的 $N$ 天里，思考每天如何吃零食。为此，他制定了以下规则：

• 每天早上、中午和晚上各吃一次零食。
• 每次只能选择吃“曲奇”“巧克力”或“蛋糕”中的一种。
• 不能连续两次吃同一种零食。（第 $i$ 天晚上的零食和第 $i+1$ 天早上的零食也不能相同。）
• 早上只能选择吃“曲奇”或“巧克力”。

请计算在 $N$ 天内，总共 $3N$ 次吃零食的安排中，满足上述所有规则的方案数，并将答案对 $10^9+7$ 取模后输出。

此外，第 $1$ 天早上可以选择吃“曲奇”或“巧克力”，且やむなく君拥有三种零食的数量都足够多。

输入为以下格式，从标准输入读取：

$N$

请输出一个整数，表示满足条件的吃零食方案数，对 $10^9+7$ 取模。

限制

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

部分得分

本题设有部分得分。

• 对于 $N \leq 10^5$ 的输入，答对可获得 $300$ 分。

样例解释 1

用“ク”表示曲奇，“ケ”表示蛋糕，“チ”表示巧克力，则 $(早, 中, 晚) = (ク, ケ, ク), (ク, ケ, チ), (ク, チ, ク), (ク, チ, ケ), (チ, ケ, ク), (チ, ケ, チ), (チ, ク, ケ), (チ, ク, チ)$ 共 $8$ 种方案。注意不能连续吃同一种零食，且早上不能吃蛋糕。

由 ChatGPT 4.1 翻译