题目描述

You have just finished cooking for some diners at the Infinite House of Pancakes. There are $\mathbf{S}$ stacks of pancakes in all, and you have arranged them in a line, such that the i-th stack from the left (counting starting from 1) has $\mathbf{P}_\mathbf{i}$ pancakes.

Your supervisor was about to bring out the stacks to the customers, but then it occurred to her that a picture of the stacks might make for a good advertisement. However, she is worried that there might be too many stacks, so she intends to remove the $\mathbf{L}$ leftmost stacks and the $\mathbf{R}$ rightmost stacks, where $\mathbf{L}$ and $\mathbf{R}$ are nonnegative integers such that $\mathbf{L} + \mathbf{R} \leq \mathbf{S} - 3$. (Notice that at least 3 stacks of pancakes will remain after the removal.)

Your supervisor also thinks the remaining stacks will look aesthetically pleasing if they have the pyramid property. A sequence of $\mathbf{N}$ stacks of heights $\mathbf{H}_1, \mathbf{H}_2, \ldots, \mathbf{H}_\mathbf{N}$ has the pyramid property if there exists an integer $\mathbf{j}$ ($1 \leq \mathbf{j} \leq \mathbf{N}$) such that $\mathbf{H}_1 \leq \mathbf{H}_2 \leq \ldots \leq \mathbf{H}_{\mathbf{j}-1} \leq \mathbf{H}_\mathbf{j}$ and $\mathbf{H}_\mathbf{j} \geq \mathbf{H}_{\mathbf{j}+1} \geq \ldots \geq \mathbf{H}_{\mathbf{N}-1} \geq \mathbf{H}_\mathbf{N}$. (It is possible that this sequence might not look much like a typical "pyramid" — a group of stacks of the same size has the pyramid property, and so does a group in which the stack heights are nondecreasing from left to right, among other examples.)

Note that the sequence of stacks remaining after your supervisor removes the $\mathbf{L}$ leftmost and $\mathbf{R}$ rightmost stacks might not yet have the pyramid property... but you can fix that by adding pancakes to one or more of the stacks! The pyramidification cost of a sequence of stacks is the minimum total number of pancakes that must be added to stacks to give the sequence the pyramid property.

While your manager is carefully deciding which values of $\mathbf{L}$ and $\mathbf{R}$ to choose, you have started to wonder what the sum of the pyramidification costs over all valid choices of $\mathbf{L}$ and $\mathbf{R}$ is. Compute this sum, modulo the prime $10^9+7$ ($1000000007$).

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each begins with one line containing one integer $\mathbf{S}$: the number of stacks of pancakes. Then, there is one more line containing $\mathbf{S}$ integers $\mathbf{P}_1, \mathbf{P}_2, \ldots, \mathbf{P}_\mathbf{S}$. The i-th of these is the number of pancakes in the i-th stack from the left.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the sum of the pyramidification costs over all valid choices of $\mathbf{L}$ and $\mathbf{R}$, modulo the prime $10^9+7$ ($1000000007$).

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

提示

Sample Explanation

In Sample Case #1, your supervisor must choose $\mathbf{L} = 0$ and $\mathbf{R} = 0$, so that is the only scenario you need to consider. The optimal strategy for that scenario is to add a single pancake to the middle stack. Although the resulting sequence of stacks looks flat, notice that it has the pyramid property; in fact, any index will work as the $\mathbf{j}$ value.

In Sample Case #2, here are all possible choices of $\mathbf{L}$ and $\mathbf{R}$, the corresponding remaining stacks, and what you should do in each scenario.

• $\mathbf{L} = 0$, $\mathbf{R} = 0$: $\mathbf{H} = [1 \ 6 \ 2 \ 5 \ 7]$. The optimal solution is to add four pancakes to the third stack and one pancake to the fourth stack. Then we have $[1 \ 6 \ 6 \ 6 \ 7]$, which has the pyramid property with $\mathbf{j} = 5$.
• $\mathbf{L} = 0$, $\mathbf{R} = 1$: $\mathbf{H} = [1 \ 6 \ 2 \ 5]$. The optimal solution is to add three pancakes to the third stack. Then we have $[1 \ 6 \ 5 \ 5]$, which has the pyramid property with $\mathbf{j} = 2$.
• $\mathbf{L} = 0$, $\mathbf{R} = 2$: $\mathbf{H} = [1 \ 6 \ 2]$. This already has the pyramid property with $\mathbf{j} = 2$.
• $\mathbf{L} = 1$, $\mathbf{R} = 0$: $\mathbf{H} = [6 \ 2 \ 5 \ 7]$. The optimal solution is to add four pancakes to the second stack and one pancake to the third stack. Then we have $[6 \ 6 \ 6 \ 7]$, which has the pyramid property with $\mathbf{j} = 4$.
• $\mathbf{L} = 1$, $\mathbf{R} = 1$: $\mathbf{H} = [6 \ 2 \ 5]$. The optimal solution is to add three pancakes to the second stack. Then we have $[6 \ 5 \ 5]$, which has the pyramid property with $\mathbf{j} = 1$.
• $\mathbf{L} = 2$, $\mathbf{R} = 0$: $\mathbf{H} = [2 \ 5 \ 7]$. This already has the pyramid property with $\mathbf{j} = 3$.

So the answer is $(5 + 3 + 0 + 5 + 3 + 0)$ modulo $(10^9 + 7)$, which is $16$.

In Sample Case #3, we only need to add extra pancakes to create the pyramid property when $\mathbf{L} = 0$ and $\mathbf{R} = 0$. In that case, it is optimal to add $999999999$ pancakes to each of the second and third stacks. (We hope the diners are hungry!) So the answer is $(999999999 + 999999999)$ modulo $(10^9 + 7) = 999999991$.

Limits

• $1 \leq \mathbf{T} \leq 100$.
• $1 \leq \mathbf{P}_\mathbf{i} \leq 10^9$, for all $\mathbf{i}$.

Test set 1 (5 Pts, Visible)

• $\mathbf{S} = 3000$, for up to 20 test cases.
• $3 \leq \mathbf{S} \leq 500$, for all remaining cases.

Test set 2 (17 Pts, Hidden)

• $\mathbf{S} = 10^6$, for up to 1 test case.
• $\mathbf{S} = 10^5$, for up to 3 test cases.
• $3 \leq \mathbf{S} \leq 10000$, for all remaining cases.