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
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