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 翻译