This time Panda is doing great. He is good with mathematical problems. His teacher decided to puzzle him with summation problems.

Consider the following definitions, assuming 1-based indexing:

In the computation of B, one can choose +1 or -1 to multiply, for each arr[i].
Also, you are allowed to re-order the elements of arr, beforehand.

Help him find the maximum possible value of C.

Input Format
The first line contains T, the number of test cases.
Then N numbers follow.

Output Format
Output the query of Panda in single line. Since the answer can be very large, mod it with 1000000007.

Constraints

1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
-10^9 ≤ arr[i] ≤ 10^9

Instructions
Write modular code
Comment your code properly

SAMPLE INPUT
1
4
1 2 3 4

SAMPLE OUTPUT
40

见题面

见题面