問題文

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

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

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

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

入力

\(N\)

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

出力

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

サンプル

2

2

4

8

8

7208

10

605864