配点 : 400 点
問題文
你喜欢吃甜食。今天 1 从今天开始 N 我决定花几天时间思考如何吃甜食。因此,我们制定以下规则。
- 每天早上、中午和晚上都会提供糖果。 吃 3 次。
- 每个人吃的糖果是“饼干”、“巧克力”或“蛋糕”。 1 。
- 同样的糖果 2 不要连续吃两次。 ( i 当天晚上 (i+1) 这也适用于当天的早上。 )
- 早上吃的甜食应该是饼干或巧克力。
N 日間、合計 3N 满足上述所有规则的甜食吃法组合有多少种? 计算除以 10^9+7 后的余数。
此外,1 第一天早上,你可以吃“饼干”或“巧克力”。 3 假设你有足够的各种糖果。
制約
- 1\le N\le 10^{18}
- N 是一个整数
部分点
这个问题有部分要点。 如果您正确回答满足
- N \leq 10^5 的输入, 将授予300 积分。
入力
输入是按以下格式从标准输入给出的。
N
出力
回答 请在 1 行输出。
入力例 1
1
出力例 1
8
饼干用“ku”表示,蛋糕用“ke”表示,巧克力用“chi”表示。
(朝、昼、晩) = (ku, ke, ku), (ku, ke, chi), (ku, chi, ku), (ku, chi, ke), (chi, ke, ku), (chi, ke, chi), (chi, ku, ke), (chi, ku, chi)
的 8 是的。请注意,不要连续吃同样的糖果,早上不要吃蛋糕。
入力例 2
2
出力例 2
40
1 当天晚上 2 第一天早上不要吃同样的甜食。
入力例 3
100000
出力例 3
607318103