配点 : $600$ 点

問題文

$N$ 本の木が左右一列に並んでおり、左から $i\, (1 \leq i \leq N)$ 本目の木 $i$ の高さは $H_i$ です。

あなたは、好きな順番でこれら $N$ 本の木を全て伐採します。具体的には、 $(1,2, \ldots, N)$ の並び替えによって得られるある順列 $P$ について、$i=1,2,3,...,N$ の順に、

• $H_{P_i-1}+H_{P_i}+H_{P_i+1}$ のコストを支払った後、木 $P_i$ を伐採する。すなわち、$H_{P_i}$ を $0$ にする。

という操作を行います。ただし、$H_0=0,H_{N+1}=0$ とします。

言い換えると、ある木を伐採するのにかかるコストは木を伐採する直前での、その木と両隣の木の高さの総和となります。

支払うコストの総和が最小となるような $P$ の個数を求めてください。答えは非常に大きくなる可能性があるので、$(10^9+7)$ で割った余りを出力してください。

制約

• $1 \leq N \leq 4000$
• $1 \leq H_i \leq 10^9$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

$H_1$ $H_2$ $\ldots$ $H_N$

出力

支払うコストの総和が最小となるような $P$ の個数を $(10^9+7)$ で割った余りを出力せよ。

3
4 2 4

2

支払うコストの総和が最小となるような $P$ は、$(1,3,2)$ と $(3,1,2)$ の $2$ つです。以下、木の伐採の例を示します。

$P=(1,3,2)$ のとき

• 最初に木 $1$ を伐採する。この時に支払うコストは $H_0+H_1+H_2=6$ である。
• 次に木 $3$ を伐採する。この時に支払うコストは $H_2+H_3+H_4=6$ である。
• 最後に木 $2$ を伐採する。この時に支払うコストは $H_1+H_2+H_3=2$ である。

支払うコストの総和は $14$ となります。

3
100 100 100

6

15
804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422 25202363 350490028 783368691 102520060 44897764

54537651

$(10^9+7)$ で割った余りを出力することに注意してください。