POWERSUM - Sum of Subsets

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

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

hide comments
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
2020-05-18 21:18:27
Even when using stdin/stdout on python, you get TLE.
2015-05-31 20:40:47 Rishabh Joshi
printing it modulo 1000000009 cost me 2 WA :P
2012-10-11 21:32:25 bruce wayne
dont deserve to be in tutorial even
2012-10-11 14:10:02 Naman
Tutorial..
2012-10-08 21:51:26 Luis Arguello
Same code, python got TLE and C got AC.
2012-10-03 12:42:51 (Tjandra Satria Gunawan)(曾毅昆)
easy task :-P
EDIT: warning, bad input formating!

Last edit: 2012-10-02 14:40:45
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.