SUMMATION - SUMMATION


You are given an array of integer. You have to find the sum of all possible subsequences sum of the array. For example: The given array of length n = 3 is {1, 2, 3}. All the subsequences 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-separated integers. 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 the 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
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.

sas1905: 2017-07-22 19:47:14

Take Care of MOD value..!!


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