Math Encoder

Professor Math is working on a secret project and has run into a problem: a list of numbers must be encoded into a single number as efficiently as possible. After much research, Professor Math found a 3 step process that encodes the numbers best:

1. The first step is to find every non-empty subset of the list of numbers, and for each subset find the difference between the largest and smallest numbers (the largest minus the smallest). If a subset holds only one number, that number is both the largest and the smallest. The whole set also counts as a subset.
2. Then add up all the differences to get the final encoded number.
3. The number can be large, so output it modulo 109 + 7 (1000000007).

The professor shares an example and its explanation below. Given a list of numbers, can you help the professor build an efficient function that computes the final encoded number?

The first line of the input gives the number of test cases, T. Then follow T test cases, each defined by 2 lines:

1. The first line gives a positive number N, the number of numbers in the list.
2. The second line contains a list of N positive integers Ki, sorted in non-decreasing order.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the final encoded number.

The output can be a very large number, so you only need to output the remainder of the result divided by the prime 109 + 7 (1000000007).

• 1 ≤ T ≤ 25.
• 1 ≤ Ki ≤ 10000, for all i.
• Ki ≤ Ki+1, for all i < N - 1.

1. Find every subset and take the difference between the largest and smallest numbers:

   • [3], largest-smallest = 3 - 3 = 0.
   • [6], largest-smallest = 6 - 6 = 0.
   • [7], largest-smallest = 7 - 7 = 0.
   • [9], largest-smallest = 9 - 9 = 0.
   • [3, 6], largest-smallest = 6 - 3 = 3.
   • [3, 7], largest-smallest = 7 - 3 = 4.
   • [3, 9], largest-smallest = 9 - 3 = 6.
   • [6, 7], largest-smallest = 7 - 6 = 1.
   • [6, 9], largest-smallest = 9 - 6 = 3.
   • [7, 9], largest-smallest = 9 - 7 = 2.
   • [3, 6, 7], largest-smallest = 7 - 3 = 4.
   • [3, 6, 9], largest-smallest = 9 - 3 = 6.
   • [3, 7, 9], largest-smallest = 9 - 3 = 6.
   • [6, 7, 9], largest-smallest = 9 - 6 = 3.
   • [3, 6, 7, 9], largest-smallest = 9 - 3 = 6.

2. Find the sum of the differences computed in the previous step: 3+4+6+1+3+2+4+6+6+3+6 = 44.

3. Find the answer modulo 109 + 7 (1000000007): 44 % 1000000007 = 44