F - 森林砍伐

分数：$600$分

题目描述

有 $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)$ 取模后输出。

约束

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

有两种使得砍伐总花费最小的排列：$(1,3,2)$ 和 $(3,1,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)$ 取模后的结果。