팬케이크 피라미드

여러 손님을 위해 무한한 팬케이크의 집에서 요리를 막 마쳤다. 팬케이크 더미는 모두 S개이며, 왼쪽에서부터 세었을 때(인덱스는 1부터 시작한다) i번째 더미에 팬케이크가 $P_{i}$개 있도록 이들을 한 줄로 배치했다.

관리자는 더미를 손님들에게 내놓으려 했지만, 이 더미들의 사진이 좋은 광고가 될 수도 있겠다는 생각이 들었다. 그러나 더미가 너무 많을까 봐 걱정되어, 가장 왼쪽의 L개 더미와 가장 오른쪽의 R개 더미를 제거하려 한다. 여기서 L과 R은 L + R ≤ S - 3을 만족하는 음이 아닌 정수이다. (제거한 뒤에도 팬케이크 더미가 적어도 3개 남는다는 점에 유의하라.)

또한 관리자는 남은 더미들이 피라미드 성질을 가지면 보기 좋을 것이라고 생각한다. 높이가 $H_{1}$, $H_{2}$, ... , $H_{N}$인 N개 더미의 수열은, $H_{1}$ ≤ $H_{2}$ ≤ ... ≤ $H_{j-1}$ ≤ $H_{j}$이고 $H_{j}$ ≥ $H_{j+1}$ ≥ ... ≥ $H_{N-1}$ ≥ $H_{N}$이 되게 하는 정수 j (1 ≤ j ≤ N)가 존재할 때 피라미드 성질을 가진다. (이 수열은 전형적인 "피라미드"와 별로 닮지 않았을 수도 있다. 크기가 모두 같은 더미들의 집합도 피라미드 성질을 가지며, 더미의 높이가 왼쪽에서 오른쪽으로 갈수록 감소하지 않는 집합도 피라미드 성질을 가진다. 이 밖에도 여러 예가 있다.)

관리자가 가장 왼쪽의 L개 더미와 가장 오른쪽의 R개 더미를 제거한 뒤 남은 더미의 수열은 아직 피라미드 성질을 가지지 않을 수도 있다는 점에 유의하라... 하지만 하나 이상의 더미에 팬케이크를 추가하면 이를 고칠 수 있다! 더미 수열의 피라미드화 비용은 그 수열이 피라미드 성질을 가지게 하기 위해 더미에 추가해야 하는 팬케이크의 총개수의 최솟값이다.

관리자가 어떤 L과 R 값을 선택할지 신중하게 결정하는 동안, 가능한 모든 L과 R의 선택에 대한 피라미드화 비용의 합이 얼마인지 궁금해졌다. 이 합을 소수 $10^{9}$+7 (1000000007)로 나눈 나머지를 계산하라.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 모든 i에 대해 1 ≤ $P_{i}$ ≤ $10^{9}$.

테스트 세트 1 (공개)

최대 20개의 테스트 케이스에서 S = 3000. 나머지 모든 케이스에서 3 ≤ S ≤ 500.

테스트 세트 2 (비공개)

최대 1개의 테스트 케이스에서 S = $10^{6}$. 최대 3개의 테스트 케이스에서 S = $10^{5}$. 나머지 모든 케이스에서 3 ≤ S ≤ 10000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 팬케이크 더미의 수를 나타내는 정수 S가 담긴 한 줄로 시작한다. 그다음 줄에는 S개의 정수 $P_{1}$, $P_{2}$, ..., $P_{S}$가 주어진다. 이 중 i번째 정수는 왼쪽에서 i번째 팬케이크 더미에 있는 팬케이크의 개수이다.

각 테스트 케이스마다 Case #x: y을 담은 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(1부터 시작한다), y는 가능한 모든 L과 R의 선택에 대한 피라미드화 비용의 합을 소수 $10^{9}$+7 (1000000007)로 나눈 나머지이다.

예제 케이스 #1에서는 관리자가 L = 0, R = 0을 선택해야 하므로, 이것이 고려해야 할 유일한 경우이다. 이 경우의 최적 전략은 가운데 더미에 팬케이크 하나를 추가하는 것이다. 그 결과로 만들어진 더미의 수열은 평평해 보이지만 피라미드 성질을 가진다는 점에 유의하라. 실제로 어느 인덱스든 j의 값으로 사용할 수 있다.

예제 케이스 #2에서 가능한 모든 L과 R의 선택, 그에 따라 남는 더미, 각 경우에 해야 할 일은 다음과 같다.

• L = 0, R = 0: $H = [1 6 2 5 7]$. 최적해는 세 번째 더미에 팬케이크 네 개를, 네 번째 더미에 팬케이크 하나를 추가하는 것이다. 그러면 $[1 6 6 6 7]$이 되며, 이는 j = 5일 때 피라미드 성질을 가진다.

• L = 0, R = 1: $H = [1 6 2 5]$. 최적해는 세 번째 더미에 팬케이크 세 개를 추가하는 것이다. 그러면 $[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]$. 최적해는 두 번째 더미에 팬케이크 네 개를, 세 번째 더미에 팬케이크 하나를 추가하는 것이다. 그러면 $[6 6 6 7]$이 되며, 이는 j = 4일 때 피라미드 성질을 가진다.

• L = 1, R = 1: $H = [6 2 5]$. 최적해는 두 번째 더미에 팬케이크 세 개를 추가하는 것이다. 그러면 $[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이다.