問題文

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

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

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

図: $4\times 4$の例。

入力

$N$

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

出力

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

サンプル

2

2

4

8

8

7208

10

605864