問題一覧 > 通常問題

No.1136 Four Points Tour

レベル : / AI推定難易度 : 700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 112
作問者 : leafirby / テスター : null
お気に入りにしたユーザー ProblemId : 4746 / 自分の提出
問題文最終更新日: 2020-07-24 05:46:05
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

There are $4$ points $\rm{A,B,C,D}$, and null-kun is currently at point $\rm{A}$. (For convenience, let the current time be second $0$.)
null-kun repeatedly moves, every $1$ second, to one of the $3$ points where he is not currently located. Find the number of ways of moving such that null-kun is at point $\rm{A}$ after $N$ seconds.
However, since the answer can be very large, output the remainder when divided by $10^9+7$.

Input

$N$

$1\le N \le 10^{18}$
$N$ is an integer.
However, test cases satisfying $10^6 < N$ do not affect the judgment of correctness. (They exist as evil cases.)

Output

Output the remainder of the answer when divided by $10^9+7$, followed by a newline.

Sample

Sample 1
Input
3
Output
6

  • $\rm{A\rightarrow B\rightarrow C\rightarrow A}$
  • $\rm{A\rightarrow B\rightarrow D\rightarrow A}$
  • $\rm{A\rightarrow C\rightarrow B\rightarrow A}$
  • $\rm{A\rightarrow C\rightarrow D\rightarrow A}$
  • $\rm{A\rightarrow D\rightarrow B\rightarrow A}$
  • $\rm{A\rightarrow D\rightarrow C\rightarrow A}$
These $6$ ways of moving are possible.

Sample 2
Input
334
Output
724282422

Output the remainder when divided by $10^9+7$.

Sample 3
Input
1000000000000000000
Output
561584175

Test cases satisfying $10^6 < N \le 10^{18}$ do not affect the judgment of correctness for this problem.

Source (the problem statement has been partially modified)

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。