← 返回题目列表

AtCoder · cpsco2019_s1_d

D. 甜点策划

中文机器翻译题面 查看原题

配点 : 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