問題一覧 > 通常問題

No.541 3 x N グリッド上のサイクルの個数

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 31
作問者 : Ryuhei MoriRyuhei Mori / テスター : はむこはむこ
2 ProblemId : 1725 / 出題時の順位表
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。