Score : $600$ points

问题描述

有 $N$ 棵树从左至右排成一行。第 $i$ 棵树（$1 \leq i \leq N$）从左边算起，即树 $i$，其高度为 $H_i$。

现在你将按照你喜欢的顺序砍倒这 $N$ 棵树。具体来说，你需要选择一个 $(1, 2, \ldots, N)$ 的排列 $P$，并按照以下方式依次对 $i=1, 2, 3, ..., N$ 进行操作：

• 砍倒树 $P_i$，即将 $H_{P_i}$ 设置为 $0$，此时的成本为 $H_{P_i-1}+H_{P_i}+H_{P_i+1}$。

这里，我们约定 $H_0=0$，$H_{N+1}=0$。

换句话说，砍倒一棵树的成本是砍倒之前该树及其相邻两棵树的总高度之和。

找出那些能使得砍倒所有树木的总成本最小的排列 $P$ 的个数。由于这个计数可能非常大，请输出模 $(10^9+7)$ 后的结果。

以上为通义千问 qwen-max 翻译，仅供参考。

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)$.

update @ 2024/3/10 09:23:45