404530: GYM101532 J The Hell Boy

Since the problem set was hard, here is an easy task for you to solve.

You are given an array a consisting of n integers, and your task is to calculate the summation of the multiplication of all subsets of array a. (See the note for more clarifications)

A subset of an array a is defined as a set of elements that can be obtained by deleting zero or more elements from the original array a.

The first line contains an integer T, where T is the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 10⁵), where n is the size of array a.

The second line of each test case contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁶), giving the array a.

For each test case, print a single line containing the summation of the multiplication of all subsets of array a. Since this number may be too large, print the answer modulo 10⁹ + 7.

3
3
1 2 3
2
3 5
1
4512

23
23
4512

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

In the first test case, the array a has 6 subsets, and the answer is calculated as follow: