Submit | All submissions | Best solutions | Back to list |

## 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 2Output: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 |