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