[ABC209F] Deforestation

$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$。

[problemUrl]: https://atcoder.jp/contests/abc209/tasks/abc209_f $ 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) $ で割った余りを出力せよ。

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) $ で割った余りを出力することに注意してください。