問題文

次の条件を満たす長さ $N$ の整数列 $A$ の通り数を求めてください。ただし、この値は非常に大きくなる場合があるので ${10}^9+7$ で割った時の余りを出力してください。

条件：以下の式を満たすような長さ $N$ の $1$ 以上 $N$ 以下の整数列 $B$ が存在する。ただし、$med(x,y,z)$ は $3$ つの値 $\{x,y,z\}$ の中央値を表す。

$A_1=med(1,B_1,N)$
$A_2=med(med(1,B_1,N-1),B_2,N)$
$A_3=med(med(med(1,B_1,N-2),B_2,N-1),B_3,N)$
　$⋮$
$A_i=med(med(med(\dots med(\dots med(med(1,B_1,N-i+1),B_2,N-i+2),\dots ,B_j,N-i+j)\dots ),B_{i-1},N-1),B_i,N)$
　$⋮$
$A_N=med(med(med(\dots med(\dots med(med(1,B_1,1),B_2,2),\dots ,B_j,j)\dots ),B_{N-1},N-1),B_N,N)$

※サンプルを参考にしてください

入力

$N$

$1\le N\le 3,000$

出力

条件を満たす整数列 $A$ の通り数を ${10}^9+7$ で割った時の余りを出力してください。最後に改行してください。

サンプル

6

1448

1

1

100

328638438