POWERSUM - Sum of Subsets

no tags 

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

hide comments
nadstratosfer: 2020-05-19 18:33:46

Easily passes in pure Python as long as correct algorithm is used.
https://www.spoj.com/ranks/POWERSUM/lang=PYTH%202.7

krishp: 2020-05-18 21:18:27

Even when using stdin/stdout on python, you get TLE.

Rishabh Joshi: 2015-05-31 20:40:47

printing it modulo 1000000009 cost me 2 WA :P

bruce wayne : 2012-10-11 21:32:25

dont deserve to be in tutorial even

Naman: 2012-10-11 14:10:02

Tutorial..

Luis Arguello: 2012-10-08 21:51:26

Same code, python got TLE and C got AC.

(Tjandra Satria Gunawan)(曾毅昆): 2012-10-03 12:42:51

easy task :-P
EDIT: warning, bad input formating!

Last edit: 2012-10-02 14:40:45

Added by:Apoorv Gupta
Date:2012-10-02
Time limit:0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Self