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