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 \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 翻译