J. The Hell Boy
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Since the problem set was hard, here is an easy task for you to solve.

You are given an array a consisting of n integers, and your task is to calculate the summation of the multiplication of all subsets of array a. (See the note for more clarifications)

A subset of an array a is defined as a set of elements that can be obtained by deleting zero or more elements from the original array a.

Input

The first line contains an integer T, where T is the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 105), where n is the size of array a.

The second line of each test case contains n integers a1, a2, ..., an (1 ≤ ai ≤ 106), giving the array a.

Output

For each test case, print a single line containing the summation of the multiplication of all subsets of array a. Since this number may be too large, print the answer modulo 109 + 7.

Example
Input
3
3
1 2 3
2
3 5
1
4512
Output
23
23
4512
Note

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

In the first test case, the array a has 6 subsets, and the answer is calculated as follow:

(1) + (2) + (3) + (1 × 2) + (1 × 3) + (2 × 3) + (1 × 2 × 3) = 23
.