No.770 Median Sequence
Pulmn問題文
次の条件を満たす長さ $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)$
$\vdots$
$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)$
$\vdots$
$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$ で割った時の余りを出力してください。最後に改行してください。
サンプル
サンプル1
入力
6
出力
1448
例えば $A=(1,2,6,5,4,6)$ は $B=(1,2,6,3,1,6)$ とすると、次の式を満たすので条件を満たします。
$A_1=med(1,B_1,6)$
$A_2=med(med(1,B_1,5),B_2,6)$
$A_3=med(med(med(1,B_1,4),B_2,5),B_3,6)$
$A_4=med(med(med(med(1,B_1,3),B_2,4),B_3,5),B_4,6)$
$A_5=med(med(med(med(med(1,B_1,2),B_2,3),B_3,4),B_4,5),B_5,6)$
$A_6=med(med(med(med(med(med(1,B_1,1),B_2,2),B_3,3),B_4,4),B_5,5),B_6,6)$
サンプル2
入力
1
出力
1
サンプル3
入力
100
出力
328638438
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。