No.621 3 x N グリッド上のドミノの置き方の数
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 31
作問者 :
しらっ亭
/ テスター :
roiti46
タグ : / 解いたユーザー数 31
作問者 :
しらっ亭
/ テスター :
roiti46
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。