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
fuggu_13: 2018-03-25 22:33:33

AC in one go!! My 50th :D

prakash1108: 2018-03-20 15:38:30

Easy af AC in 1 Go :xD

venkat016: 2018-01-16 15:44:09

any tricky test cases. test with all test cases in spoj toolkit but still get WA :(

nadstratosfer: 2017-12-18 16:52:06

jaykay12, mahilewets' comment below is a big hint (a Python program doing nothing takes 0.02s on SPOJ).

jaykay12: 2017-12-17 20:10:05

Recursive approach giving TLE & iterative using bitwise giving WA :( Any suggestions?

mahilewets: 2017-08-20 10:43:22

Python 3.5 AC 0.05 sec 28 MB

ayushgupta1997: 2017-08-13 11:18:41

@aditya_97 element can occur more than once but you should treat them different ,don't know why?

aditya_97: 2017-07-24 14:19:04

can same element occur more than once ?

vengatesh15: 2017-07-24 12:34:12

easy one used big int

aman224: 2017-07-22 21:30:00

Easy :p. Although its strange that no constraints are sprecified for the array elements , and the value of MOD is 10^8+7.


Added by:Bhadra
Date:2017-07-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All