## 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

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

 Added by: Bhadra Date: 2017-07-22 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA PYTHON PYPY PYTHON3