Solve the programming task below in a Python markdown code block.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Princess Rupsa saw one of her friends playing a special game. The game goes as follows:

N+1 numbers occur sequentially (one at a time) from A_{0} to A_{N}.
You must write the numbers on a sheet of paper, such that A_{0} is written first. The other numbers are written according to an inductive rule — after A_{i-1} numbers have been written in a row, then A_{i} can be written at either end of the row. That is, you first write A_{0}, and then A_{1} can be written on its left or right to make A_{0}A_{1} or A_{1}A_{0}, and so on.
A_{i} must be written before writing A_{j}, for every i < j.
For a move in which you write a number A_{i} (i>0), your points increase by the product of A_{i} and its neighbour. (Note that for any move it will have only one neighbour as you write the number at an end).
Total score of a game is the score you attain after placing all the N + 1 numbers.

Princess Rupsa wants to find out the sum of scores obtained by all possible different gameplays. Two gameplays are different, if after writing down all N + 1 numbers, when we read from left to right, there exists some position i, at which the gameplays have a_{j} and a_{k} written at the i^{th} position such that j ≠ k. But since she has recently found her true love, a frog Prince, and is in a hurry to meet him, you must help her solve the problem as fast as possible. Since the answer can be very large, print the answer modulo 10^{9} + 7.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases.		
The first line of each test case contains a single integer N. 
The second line contains N + 1 space-separated integers denoting A_{0} to A_{N}.
 
------ Output ------ 

For each test case, output a single line containing an integer denoting the answer.

------ Constraints ------ 

1 ≤ T ≤ 10
1 ≤ N ≤ 10^{5}
1 ≤ A_{i} ≤ 10^{9}

------ Sub tasks ------ 

Subtask #1: 1 ≤ N ≤ 10 (10 points)
Subtask #2: 1 ≤ N ≤ 1000 (20 points)
Subtask #3: Original Constraints (70 points)

----- Sample Input 1 ------ 
2

1

1 2

2

1 2 1
----- Sample Output 1 ------ 
4

14
----- explanation 1 ------ 

There are 2 possible gameplays. A0A1 which gives score of 2 and  A1A0 which also gives score of 2. So the answer is 2 + 2 = 4