Description

你刚刚在“无限煎饼屋”为一些食客完成了烹饪。总共有 $S$ 堆煎饼，你将它们排成一行，第 $i$ 堆（从左到右，从 1 开始计数）有 $P_i$ 张煎饼。

你的主管正准备把这些煎饼端给顾客，但她突然想到，给这些煎饼堆拍一张照片可能会成为很好的广告。不过，她担心煎饼堆太多，于是打算移除最左边的 $L$ 堆和最右边的 $R$ 堆，其中 $L$ 和 $R$ 是非负整数，满足 $L + R \leq S - 3$。也就是说，移除后至少还会剩下 3 堆煎饼。

你的主管还认为，剩下的煎饼堆如果满足“金字塔属性”会更美观。对于一组高度为 $H_1, H_2, \ldots, H_N$ 的 $N$ 堆煎饼，如果存在一个整数 $j$（$1 \leq j \leq N$），使得 $H_1 \leq H_2 \leq \ldots \leq H_{j-1} \leq H_j$ 且 $H_j \geq H_{j+1} \geq \ldots \geq H_{N-1} \geq H_N$，那么这组煎饼堆就具有金字塔属性。（注意，这样的序列不一定看起来像传统的“金字塔”——比如所有堆高度相同的序列也满足金字塔属性，或者高度从左到右单调不减的序列也满足。）

注意，经过移除 $L$ 个最左和 $R$ 个最右的煎饼堆后，剩下的序列可能还不满足金字塔属性……但你可以通过给某些堆添加煎饼来修正！一组煎饼堆的“金字塔化代价”定义为：使该序列满足金字塔属性所需添加的煎饼总数的最小值。

当你的主管还在仔细考虑 $L$ 和 $R$ 的取值时，你开始思考：所有合法的 $L$ 和 $R$ 取值下，金字塔化代价之和是多少？请计算这个和，并对质数 $10^9+7$（$1000000007$）取模。

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试用例。每组测试用例的第一行为一个整数 $S$，表示煎饼堆的数量。接下来一行有 $S$ 个整数 $P_1, P_2, \ldots, P_S$，第 $i$ 个数表示从左到右第 $i$ 堆煎饼的数量。

Output Format

对于每组测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是所有合法 $L$ 和 $R$ 取值下金字塔化代价之和，对 $10^9+7$ 取模后的结果。

3
3
2 1 2
5
1 6 2 5 7
4
1000000000 1 1 1000000000

Case #1: 1
Case #2: 16
Case #3: 999999991

Hint

样例解释

在样例 1 中，你的主管只能选择 $L=0$ 且 $R=0$，所以只需考虑这一种情况。最优策略是给中间那一堆加一张煎饼。虽然最终序列看起来是平的，但它满足金字塔属性；实际上，任何一个位置都可以作为 $j$。

在样例 2 中，所有可能的 $L$ 和 $R$ 取值、剩余的煎饼堆序列及最优操作如下：

• $L=0$，$R=0$：$H=[1\ 6\ 2\ 5\ 7]$。最优解是给第三堆加 4 张煎饼，第四堆加 1 张煎饼，得到 $[1\ 6\ 6\ 6\ 7]$，此时 $j=5$。
• $L=0$，$R=1$：$H=[1\ 6\ 2\ 5]$。最优解是给第三堆加 3 张煎饼，得到 $[1\ 6\ 5\ 5]$，此时 $j=2$。
• $L=0$，$R=2$：$H=[1\ 6\ 2]$。本身就满足金字塔属性，$j=2$。
• $L=1$，$R=0$：$H=[6\ 2\ 5\ 7]$。最优解是给第二堆加 4 张煎饼，第三堆加 1 张煎饼，得到 $[6\ 6\ 6\ 7]$，此时 $j=4$。
• $L=1$，$R=1$：$H=[6\ 2\ 5]$。最优解是给第二堆加 3 张煎饼，得到 $[6\ 5\ 5]$，此时 $j=1$。
• $L=2$，$R=0$：$H=[2\ 5\ 7]$。本身就满足金字塔属性，$j=3$。

因此答案为 $(5 + 3 + 0 + 5 + 3 + 0)$ 对 $(10^9 + 7)$ 取模，即 $16$。

在样例 3 中，只有 $L=0$ 且 $R=0$ 时需要额外加煎饼使其满足金字塔属性。在这种情况下，最优解是给第二堆和第三堆各加 $999999999$ 张煎饼。（希望食客们胃口够大！）所以答案为 $(999999999 + 999999999)$ 对 $(10^9 + 7)$ 取模，结果为 $999999991$。

数据范围

• $1 \leq T \leq 100$。
• 对所有 $i$，$1 \leq P_i \leq 10^9$。

测试点 1（5 分，公开）

• $S = 3000$，最多 20 组测试用例。
• 其余测试用例满足 $3 \leq S \leq 500$。

测试点 2（17 分，隐藏）

• $S = 10^6$，最多 1 组测试用例。
• $S = 10^5$，最多 3 组测试用例。
• 其余测试用例满足 $3 \leq S \leq 10000$。

由 ChatGPT 4.1 翻译