Scooby and the Ghost

4.5

6 votes
Easy
Problem

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

Time Limit: 1
Memory Limit: 256
Source Limit:
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

Editor Image

?