No.770 Median Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 10
作問者 : PulmnPulmn
3 ProblemId : 2475 / 出題時の順位表

問題文

次の条件を満たす長さ $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

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。