問題一覧 > 通常問題

No.1500 Super Knight

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 85
作問者 : sirogamichan1 / テスター : だれ
お気に入りにしたユーザー ProblemId : 6344 / 自分の提出
問題文最終更新日: 2021-05-07 23:59:59
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
yukicoder contest 294 (順位表) の他の問題:

Problem Statement

There is an infinite $2$-dimensional grid, and a "Super Knight" is placed on one of its cells.
In $1$ move, this piece can move as follows.



More precisely, when the Super Knight is on cell $(a,b)$, it can be moved to any one of the following cells.
$(a+3, b), (a+3, b+2), (a+2, b+3), (a, b+3), (a-2, b+3), (a-3, b+2)$  $(a-3, b), (a-3, b-2), (a-2, b-3), (a, b-3), (a+2, b-3), (a+3, b-2)$

After making $N$ moves, how many cells could the Super Knight possibly be on? Find the count modulo $10^9+7$.

Input

$N$

$0\leq N\leq 10^9$

Output

Output the number of cells the Super Knight could possibly be on, modulo $10^9+7$.
Print a newline at the end.

Sample

Sample 1
Input
1
Output
12

In this case, the initial cell is not included.

If the initial cell is $(0, 0)$, the piece can move to any one of the following cells.
$(3, 0), (3, 2), (2, 3), (0, 3), (-2, 3), (-3, 2)$
$(-3, 0), (-3, -2), (-2, -3), (0, -3), (2, -3), (3, -2)$

Sample 2
Input
314159265
Output
490910278

Output the answer modulo $10^9 + 7$.

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