No.541 3 x N グリッド上のサイクルの個数
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 37
作問者 :
Ryuhei Mori
/ テスター :
はむこ
タグ : / 解いたユーザー数 37
作問者 :
Ryuhei Mori
/ テスター :
はむこ
問題文最終更新日: 2017-06-29 21:18:08
問題文
縦に4つ、横に$N+1$つ頂点が格子状に接続している無向グラフ
を $3\times N$ のグリッドと呼ぶ。$3\times N$ のグリッドに含まれる単純閉路の個数を
$10^9+7$で割った余りをもとめよ。
入力
N
$1\le N \le 10^{18}$
出力
$3\times N$ のグリッドに含まれる単純閉路の個数を$10^9+7$で割った余り。
サンプル
サンプル1
入力
1
出力
6
1x1のサイクルが3つ、2x1のサイクルが2つ、3x1のサイクルが1つで合計6つ存在する。
サンプル2
入力
20
出力
324214693
サンプル3
入力
100
出力
652583913
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。