SUMMATION  SUMMATION
You are given an array of integer. You have to find the sum of all possible subsuquences sum of the array. For example: The given array of length n = 3 is {1,2,3}. All the sequence of this array with the corresponding array Summations are:
Subsequence 
Summation 
{} 
0 
{1} 
1 
{2} 
2 
{3} 
3 
{1,2} 
3 
{1,3} 
4 
{2,3} 
5 
{1,2,3} 
6 
Total 
24 
The answer is 24.
Input
The first line of input will contain the test case T (1 <= T <= 10).There will be two lines for each test case. First line will contain the value of n(1<=n<=1000) and the next line will contain the array elements space sperated intergers. Each integer will be between 1 and 1000000000.
Output
For each case of input, output the answer of the problem in the format "Case X: Y" where X denotes the number of test case and Y denotes the answer. Answer could be very large so output the answer modulo 100000007.
Example
Input:
2
3
1 2 3
3
4 1 2
Output:
Case 1: 24
Case 2: 28
hide comments
DK...:
20190526 08:59:38
Be careful about the spaces in the output format. 

akjol2049:
20181125 10:26:25
Be careful with the mod. 10^8+7 

sanyam19:
20180628 17:39:37
Repeating nos., Pattern ,derive a Formula ,thats it... :p 

fuggu_13:
20180325 22:33:33
AC in one go!! My 50th :D 

prakash1108:
20180320 15:38:30
Easy af AC in 1 Go :xD 

venkat016:
20180116 15:44:09
any tricky test cases. test with all test cases in spoj toolkit but still get WA :( 

nadstratosfer:
20171218 16:52:06
jaykay12, mahilewets' comment below is a big hint (a Python program doing nothing takes 0.02s on SPOJ). 

jaykay12:
20171217 20:10:05
Recursive approach giving TLE & iterative using bitwise giving WA :( Any suggestions? 

mahilewets:
20170820 10:43:22
Python 3.5 AC 0.05 sec 28 MB 

ayushgupta1997:
20170813 11:18:41
@aditya_97 element can occur more than once but you should treat them different ,don't know why? 
Added by:  Bhadra 
Date:  20170722 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 