题目描述

$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)$ で割った余りを出力してください。

输入格式

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

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

输出格式

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

题目大意

$n$ 个数：$a_1,a_2,...,a_n$。

每次可以选择一个 $i$，选择的代价是 $a_{i-1}+a_i+a_{i+1}$，然后令 $a_i=0$。

求有多少种方案，使得 $a_1,a_2,...,a_n$ 都变为 $0$ 的总代价最小。特别的，$a_0=a_{n+1}=0$。

3
4 2 4

2

3
100 100 100

6

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

54537651

提示

制約

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

Sample Explanation 1

支払うコストの総和が最小となるような $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$ となります。

Sample Explanation 3

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