题目描述

有 $N$ 棵树从左到右排成一行。从左边开始，第 $i$ 棵树（$1 \leq i \leq N$），树 $i$ 的高度为 $H_i$。

现在你要按照自己喜欢的顺序砍倒所有这些 $N$ 棵树。具体而言，你将选择一个由 $(1, 2, ..., 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$ $...$ $H_N$

输出

打印最小化砍倒树木总代价的置换 $P$ 的数量，对 $(10^9+7)$ 取模后输出。

示例输入 1

3
4 2 4

示例输出 1

2

有两个最小化总代价的置换 $P$：$(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$。

示例输入 2

3
100 100 100

示例输出 2

6

示例输入 3

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

示例输出 3

54537651

记得对 $(10^9+7)$ 取模。