AT_abc209_f [ABC209F] Deforestation

题目描述

有 $N$ 棵树从左到右排成一列，从左起第 $i$ 棵树的高度为 $H_i$。

你可以以任意顺序将这 $N$ 棵树全部砍倒。具体来说，对于通过排列 $(1,2,\ldots,N)$ 得到的某个排列 $P$，依次按照 $i=1,2,3,\ldots,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$ 取模后的结果。

输入输出样例 #1

输入 #1

3
4 2 4

输出 #1

2

输入输出样例 #2

输入 #2

3
100 100 100

输出 #2

6

输入输出样例 #3

输入 #3

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

输出 #3

54537651

说明/提示

限制条件

• $1 \leq N \leq 4000$
• $1 \leq H_i \leq 10^9$
• 输入均为整数

样例解释 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$。

样例解释 3

请注意要输出对 $10^9+7$ 取模后的结果。

由 ChatGPT 4.1 翻译