The sum of a set is defined as the sum of all elements in the set. You are given a set of integers, each between 0 and 10^9. Find the total sum of the sums of each subset of the set.

Input

There are several test cases. The first line will contain T, the number of test cases.

Each of the next T test cases begin with a single integer n, the number of elements in the set, on the first line.

The second line of each test case will contain n space separated integers, the elements of the given set.

Output

For each test case, you are required to print the total sum of the sums of each subset of the set. As the answer can be quite large, print it modulo (10^9+7).

Constraints

1 <= T <= 100.

1 <= n <= 10^4.

Example

Input:
2
3
1 4 8
2
3 6

Output:
52
18