問題一覧 > 通常問題

No.621 3 x N グリッド上のドミノの置き方の数

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 30
作問者 : しらっ亭しらっ亭 / テスター : roiti46roiti46
2 ProblemId : 2031 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-12-17 22:48:43

問題文

縦に $3$ 個、横に $N$ 個のマス目からなるグリッドを $3 \times N$ のグリッドと呼ぶ。
下記の図は、$3 \times 10$ のグリッドである。

「$3 \times N$ のグリッドのマス目の上に、$1 \times 2$ サイズのドミノを、ドミノ同士が重ならないように、ドミノがグリッドからはみ出さないように、これ以上置けなくなるまで置く方法」の総数を $10^9 + 7$ で割った余りを求めよ。

ドミノは回転して使ってよい。それぞれのドミノは区別しない。
グリッドをドミノで埋め尽くす必要が無い点に注意せよ。

入力

$N$

$1 \le N \le 10^{18}$
$N$ は整数

出力

答えを1行で出力せよ。
最後に改行せよ。

サンプル

サンプル1
入力
2
出力
5

の $5$ 通りである。

等は、まだドミノを置くことができるため、数えない。

サンプル2
入力
20
出力
718700373

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