問題一覧 > 通常問題

No.93 ペガサス

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 51
作問者 : krotonkroton
2 ProblemId : 101 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:46:35

問題文

直樹くんは \(N \times N\) マスの将棋盤と \(N\) 個の「飛馬」という不思議な駒を持っています。「飛馬」とは飛車と桂馬の動きを併せ持つ駒です。

図: 「飛馬」の動き。縦横には何マスでも動ける。


ある日駒を適当に並べていると、「互いに取られないような \(N\) 個の飛馬の配置」があることを発見しました。
あなたは、この条件を満たす駒の配置のパターン数を \(10^9 + 7\) で割った余りを求めるプログラムを書いて下さい。
ただしそれぞれの駒は区別できず、またすべて上を向いているとしてください。


図: \(4\times 4\)の例。

入力

\(N\)

\(N(1\leq N\leq 1000)\) が与えられる。

出力

条件を満たす駒の配置のパターン数を \(10^9 + 7\) で割った余りを出力してください。

サンプル

サンプル1
入力
2
出力
2
サンプル2
入力
4
出力
8
サンプル3
入力
8
出力
7208
サンプル4
入力
10
出力
605864

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