github.com/captn3m0/codechef.git

---
category_name: easy
problem_code: KOL1502
problem_name: 'The Christmas Gift'
languages_supported:
    - C
    - CPP14
    - JAVA
max_timelimit: '1'
source_sizelimit: '50000'
problem_author: devuy11
problem_tester: null
date_added: 29-11-2015
tags:
    - acm15kol
    - devuy11
    - dynamic
editorial_url: 'http://discuss.codechef.com/problems/KOL1502'
time:
    view_start_date: 1451123700
    submit_start_date: 1451123700
    visible_start_date: 1451123700
    end_date: 1735669800
    current: 1493558156
layout: problem
---
All submissions for this problem are available.CodeChef has received a package of **N** ingredients from Aloo uncle and Kachori aunty as their Christmas gift. **CodeChef decides to make dishes with every possible combination of these **N** ingredients**. (**Note:** A dish with 0 ingredients is also possible. CodeChef uses it as an excuse for serving air to their airy customers). Every ingredient from the package has a taste score between **1 and 10**.

Now CodeChef has customers on two planets, planet **A** and planet **B**. People from planet **A** like all the ingredients very much. And hence for every dish given to them, planet **A** will pay CodeChef an amount, which, in Alterian dollars, equals the sum of the taste scores of all the ingredients present in the dish minus the sum of the taste scores of all the ingredients not present in the dish.

People from planet **B** don't like the ingredients at all. So for every dish given to planet **B**, planet **B** will pay CodeChef Alterian dollars equal to the sum of the taste scores of all the ingredients not present in the dish minus the sum of the taste scores of all the ingredients present in the dish.

CodeChef can only make a single dish from a particular combination of ingredients. And **they can send a dish either to planet **A** or planet **B**, but not both**. You have to find out the maximum amount of money CodeChef will make by distributing **all the dishes made** with these ingredients on planet **A** and planet **B**.

Report the maximum amount **modulo 107**.

### Input

The first line contains **T**, the number of test cases.

Each test case begins with **N**, the number of ingredients

The next line for the test case contains **N** space-separated integers, which are the taste scores of the ingredients.

### Output

For each test case, output the value as asked in a separate line.

### Constraints

- **1** ≤ **T** ≤ **100**
- **1** ≤ **N** ≤ **1000**
- **1** ≤ **Taste scores of ingredients** ≤ **10**
- **1** ≤ **Sum of N over all Test Cases** ≤ **1000**

### Example

<pre><b>Input:</b>
1
2
1 2
<b>Output:</b>
8
</pre>### Explanation

**Example case 1.** The dishes made by CodeChef and the amounts collected:

- Dish 1: Contains both ingredients: Sold to Planet A for 3 Alterian dollars.
- Dish 2: Contains first ingredients: Sold to Planet B for 1 Alterian dollars.
- Dish 3: Contains second ingredients: Sold to Planet A for 1 Alterian dollars.
- Dish 4: Does not contain any ingredients: Sold to Planet B for 3 Alterian dollars.

Total Amount : 8 Alterian dollars.