DCEPC301 - Foodie Golu

Being a big foodie Golu wants to try all the dishes available at a party but because of his increasing weight his mother does not allow him to do so. After a huge fight they both come to an agreement.

1.  The first rule of the agreement says that Golu should only eat at an interval of 10 minutes.

2.  The second rule is regarding the stalls available. There are N stalls in one line and Golu should select only one stall to eat at one time. The selected stall must lie at the n/2th position or (n/2 + 1) position (zero indexed) among all remaining stalls.

3.  Once he has selected a stall he must discard all the stalls to its left (or right) and in future can only eat from the remaining stalls. Also he can eat from a stall only once during the party, so once he has eaten from a stall, it should be discarded too.

The initial cooking speed at all the stalls is 1 unit. After doing some calculations Golu realises that the speed of cooking of the cook at every stall becomes double every 10 minutes. Depending upon the type of dish available and his eating capacity, he assigned a value to each stall such that any point of time he can eat a quantity which is equal to (value of that stall) * (current speed of cooking at that stall). Since speed is increasing exponentially he only remembers speed as speed % mod at any time.

Since he wants to eat the maximum amount of food, help him in developing a strategy to eat.

NOTE: If there are only 2 stalls left, he must choose any one stall and discard the other.

Input

First line contains T, the number of test cases. (1<=T<=5)

First line of each test case contains n, the number of stalls in the party. (1<=n<=3000)

Next line of each test case contains n space separated integers, representing the value of each of the stalls. (All values are between 1 and 3000 inclusive)

Output

Output T lines, one for each test case containing the maximum amount of food Golu can eat mod 10^9+7

Example

Input:
1
5
2 4 1 3 5

Output:
21

Explanation:

Golu can select the fourth stall first and discard all stalls to its right (i.e. discard fifth stall). Then he can select the third stall and again discard all stalls to its right (no stall to discard this time). Finally he chooses the 2nd stall. Therefore total food he can eat = 3*1 + 1*2 + 4*4 = 21.


Added by:dce coders
Date:2012-03-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem

hide comments
2012-11-12 23:18:57 Aman Gupta
Are we supposed to maximize food eaten or food eaten mod 10^9 + 7?

EDIT: food eaten

Last edit: 2012-11-13 12:03:38
2012-06-28 10:54:26 ketul shah
can anybody give large test case and also its answer
2012-05-17 13:18:05 Sidharth Gupta
@Prateek: speed = (2*speed)%mod.
2012-05-12 15:27:12 Prateek Sultania
Since speed is increasing exponentially he only remembers speed as speed % mod at any time.

Can you plz clarify what does speed%mod means?
2012-04-27 19:23:26 RAJDEEP GUPTA
what is the answer for
1
3
1 2 3?
EDIT: Its 8.

Last edit: 2012-04-28 05:03:18
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.