Scooby is stuck in a cave in barren islands. Shaggy decided to play a prank on scooby.
in his ghostly voice shaggy asks a question to the scared scooby.
the ghost(shaggy) will make scooby's way out only if he answers the following problem.
since scooby is not a nerd help him get out of the cave. the question is as follows.
Given a set S .
value of subset of s is sum of numbers in that subset.
Find sum of value of all subsets mod 10^9+7.

Note :- value of null set is 0

Input

first line contains T . no of test cases

first line of every test cases is n (set size)

second line of every test cases contains n numbers of the set x(i).

Output

print on a new line sum of value of all subsets of S mod 10^9+7 for each test case

Constraint

0 < T < 10

0 < n ≤ 100

0 ≤ x(i) ≤ 100000

SAMPLE INPUT
1
3
1 2 3

SAMPLE OUTPUT
24

Explanation

for set {1,2,3}

posssible subsets are {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

sum of value of all subset is 24

见题面

见题面