No.569 3 x N グリッドのパスの数
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 39
作問者 :
Ryuhei Mori
/ テスター :
はむこ
タグ : / 解いたユーザー数 39
作問者 :
Ryuhei Mori
/ テスター :
はむこ
問題文最終更新日: 2017-06-03 13:04:35
問題文
おねえさんは強力な力を手に入れて 26 x 26 のグリッドのパスを数えられるようになった。
しかし、その力では 3 x 1000000000000000000 のグリッドのパスを数えることができない。
おねえさんを助けよ。
ここで$3\times N$ のグリッドとは縦に4つ、横に$N+1$つ頂点が格子状に接続している無向グラフ
である。
入力
N
$1\le N \le 10^{18}$
出力
$3\times N$のグリッドの左上の頂点から右下の頂点へ同じ頂点を二度通らないで辿り着く方法の総数を$10^9+7$で割った余りを出力せよ。
サンプル
サンプル1
入力
1
出力
8
サンプル2
入力
2
出力
38
サンプル3
入力
100
出力
244451960
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。