伐木

题目描述

有 $N$ 棵树从左到右排成一排。从左数第 $i$ 棵树（$1 \le i \le N$）Tree $i$ 的高度为 $H_i$。

现在按你喜欢的某种顺序砍掉全部 $N$ 棵树。形式上，你选择一个 $(1, 2, \ldots, N)$ 的排列 $P$，并按顺序对每个 $i=1, 2, 3, \ldots, N$ 执行以下操作：

砍掉 Tree $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)$ 取模的结果。

输入格式

输入按以下格式从标准输入给出：

$N$
$H_1$ $H_2$ $\ldots$ $H_N$

输出格式

输出使总体代价最小的排列 $P$ 的个数对 $(10^9+7)$ 取模的结果。

样例

3
4 2 4

2

使总体代价最小的排列 $P$ 有两个：$(1,3,2)$ 和 $(3,1,2)$。

下面以 $P=(1,3,2)$ 为例展示砍树过程。

首先，砍掉 Tree $1$，代价为 $H_0+H_1+H_2=6$。

接着，砍掉 Tree $3$，代价为 $H_2+H_3+H_4=6$。

最后，砍掉 Tree $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)$ 取模后的结果。

数据范围

• $1 \le N \le 4000$
• $1 \le H_i \le 10^9$
• 输入中所有值均为整数