← 返回题目列表

AtCoder · abc209_f

F. 森林砍伐

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有 N 树木从左到右排成一排。的 i第棵树 (1 \leq i \leq N) 从左起,树 i,高度为 H_i.

现在你将砍掉所有这些 N 树按照您喜欢的顺序排列。正式地,您将选择一个排列 P of (1, 2, \ldots, N) 并对每个执行以下操作 i=1, 2, 3, ..., N 按此顺序。

  • 砍树 P_i,即设置 H_{P_i} to 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 \ldots 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).