Mani likes to live in dreams. He dreams of a hypothetical world where bodmas rule doesn't exist. In such a world , expressions are evaluated only on the basis of left-right occurence. that is the expression "1+2*3+4" is evaluated as ( ( ( 1 + 2 ) * 3 ) + 4 ) which equals to 13. Such a method of evaluation of an expression is called as !BODMAS.

In his dream, he dreamt of a list of numbers. He wanted to create an expression using this list and "*" and "+" operator. He writes these numbers separated by space , and wishes to fill each space with either a + sign or a * sign.

Now consider all such expressions , if there are n numbers in the list , then there will be n-1 spaces and hence \( 2^{n-1} \) number of expressions possible. Considering the !BODMAS rule, You need to sum up the values of all such expressions possible from a list and print them. Since the sum can go very large , print sum MODULO 1000000007.

INPUT:-
First line consist of an integer corresponding to number of testcases.
For each test cases, first line consist of the list size n, second line storing the list elements \( a_{i} \)

OUTPUT:-
For each test case print the sum of all the expressions possible evaluated using !BODMAS rule

CONSTRAINTS:- 1<=t<=5
1<=n<=100000
1<=\( a_{i} \)<=100000