Nam is playing with his cards. He has N + 1 cards, numbered from 0 to N. Card number i have a value Ai written on it.
Initially, only card number 0 is on the table. Nam will put N remaining cards 1, 2, ..., N on the table in that order. Each card have two ways to put it on the table: in the left or in the right the cards row currently on the table (see the sample test for better understanding). Therefore there are 2N ways of putting cards in total. When card valued x is put adjacent card valued y, Nam will gain x * y score more.
Nam plays his own game for fun, so he doesn't care about maximizing or minimizing his final score. He only interested in sum score of all 2N game he could make. Your task is calculate this number.
Input
The first line is T - the number of test cases. Then T test cases follow.
Each test consists of 2 lines. The first line contains a single positive integer N. The second line contains N + 1 integer numbers A0, A1, .., AN, denoting values are written on cards.
Output
For each test, print the answer. Since the answer may very large, you must print it modulo 109 + 7.
Constraints
In the second test, there are 4 ways of putting cards. 1) Put card 1 in the left, then put card 1 in the left. Score gained: 2 * 1 + 3 * 2 = 8. 2) Put card 1 in the left, then put card 2 in the right. Score gained: 2 * 1 + 3 * 1 = 5. 3) Put card 1 in the right, then put card 2 in the left. Score gained: 2 * 1 + 3 * 1 = 5. 4) Put card 1 in the right, then put card 2 in the right. Score gained: 2 * 1 + 3 * 2 = 8.