/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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) で割った余りを出力せよ。
入力例 1
3 4 2 4
出力例 1
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 となります。
入力例 2
3 100 100 100
出力例 2
6
入力例 3
15 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422 25202363 350490028 783368691 102520060 44897764
出力例 3
54537651
(10^9+7) で割った余りを出力することに注意してください。
Score : 600 points
Problem Statement
There are N trees standing in a row from left to right. The i-th tree (1 \leq i \leq N) from the left, Tree i, has the height of H_i.
You will now cut down all these N trees in some order you like. Formally, you will choose a permutation P of (1, 2, \ldots, N) and do the operation below for each i=1, 2, 3, ..., N in this order.
- Cut down Tree P_i, that is, set H_{P_i} to 0, at a cost of H_{P_i-1}+H_{P_i}+H_{P_i+1}.
Here, we assume H_0=0,H_{N+1}=0.
In other words, the cost of cutting down a tree is the total height of the tree and the neighboring trees just before doing so.
Find the number of permutations P that minimize the total cost of cutting down the trees. Since the count may be enormous, print it modulo (10^9+7).
Constraints
- 1 \leq N \leq 4000
- 1 \leq H_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N H_1 H_2 \ldots H_N
Output
Print the number of permutations P, modulo (10^9+7), that minimize the total cost of cutting down the trees.
Sample Input 1
3 4 2 4
Sample Output 1
2
There are two permutations P that minimize the total cost: (1,3,2) and (3,1,2).
Below, we will show the process of cutting down the trees for P=(1,3,2), for example.
- First, Tree 1 is cut down at a cost of H_0+H_1+H_2=6.
- Next, Tree 3 is cut down at a cost of H_2+H_3+H_4=6.
- Finally, Tree 2 is cut down at a cost of H_1+H_2+H_3=2.
The total cost incurred is 14.
Sample Input 2
3 100 100 100
Sample Output 2
6
Sample Input 3
15 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422 25202363 350490028 783368691 102520060 44897764
Sample Output 3
54537651
Be sure to print the count modulo (10^9+7).