你刚刚为一些食客烹饪完了煎饼。总共有 $S$ 叠煎饼，你将它们排成一行，使得从左往右数第 $i$ 叠（从 1 开始计数）有 $P_i$ 个煎饼。
你的主管正准备把这些煎饼端给顾客，但她突然想到，给这些煎饼拍张照可能是一个很好的广告。然而，她担心煎饼叠数太多，所以她打算移除最左边的 $L$ 叠和最右边的 $R$ 叠，其中 $L$ 和 $R$ 是非负整数，且满足 $L + R \le S - 3$。（注意，移除后至少会剩下 3 叠煎饼。）
你的主管还认为，如果剩下的煎饼叠具有“金字塔属性”，看起来会赏心悦目。一个包含 $N$ 叠煎饼的序列 $H_1, H_2, \dots, H_N$ 具有金字塔属性，如果存在一个整数 $j$ ($1 \le j \le N$)，使得 $H_1 \le H_2 \le \dots \le H_{j-1} \le H_j$ 且 $H_j \ge H_{j+1} \ge \dots \ge H_{N-1} \ge H_N$。（这个序列可能看起来不像典型的“金字塔”——例如，一组高度相同的煎饼叠具有金字塔属性，高度从左到右非递减的序列也具有金字塔属性，等等。）
注意，主管移除最左边的 $L$ 叠和最右边的 $R$ 叠后剩下的煎饼序列可能还不具备金字塔属性……但你可以通过给其中一叠或多叠煎饼增加煎饼数量来修复它！一个煎饼序列的“金字塔化成本”是指为了使该序列具有金字塔属性，必须增加的煎饼总数最小值。
当你的主管正在仔细决定选择哪些 $L$ 和 $R$ 的值时，你开始好奇所有合法的 $L$ 和 $R$ 选择下的金字塔化成本之和是多少。请计算这个总和，并对质数 $10^9+7$ ($1000000007$) 取模。
输入格式
输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $S$：煎饼叠的总数。接下来一行包含 $S$ 个整数 $P_1, P_2, \dots, P_S$，其中第 $i$ 个数表示从左往右数第 $i$ 叠煎饼的数量。
输出格式
对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是所有合法 $L$ 和 $R$ 选择下的金字塔化成本之和，对质数 $10^9+7$ ($1000000007$) 取模的结果。
数据范围
$1 \le T \le 100$ $1 \le P_i \le 10^9$，对于所有 $i$。
样例
样例输入 1
3 3 2 1 2 5 1 6 2 5 7 4 1000000000 1 1 1000000000
样例输出 1
Case #1: 1 Case #2: 16 Case #3: 999999991
说明
在样例 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。