Stud Sahil and his girlfriend X(??) are trying to find a new place in Kamand to live together as a couple. They are in a dilemma. Their friends live in different parts of the village and they want to live close to all of them. All houses in Kamand lie on a horizontal line(X-axis). There is a house on every lattice(integer) point on  this line. You are given the x-coordinates of all the friends' houses along that line in an array A of n integers {A₁, A₂, ....A_n}.

Your task is to find the sum of all the distinct coordinates where Sahil and X can select their house so that the total of the distances between their(Sahil and X) and each friend's house is minimized. Have a look at the sample I/O for better understanding.

Note that they can also live at their friends' place if required.

Since the answer can be very large, print the answer MODULO 10⁹ + 7.

Input

The first line contains the total number of test cases T. Each of the test case contains two lines. The first line of each test case contains the size of the array N. The next line contains N space separated integers, denoting the x-co-ordinates of their friends' houses.

Since the input file can be very large, it is advisable to use fast I/O.

Output

For each test case, print the answer in a single line.

Constraints

• 1 <= T <= 10
• 1 <= N <= 10⁵
• -10¹² <= A_i <= 10¹²

Subtasks

Subtask #1 (20 points):

• -10³ <= A_i <= 10³

• 1<=N<=1000

Subtask #2 (80 points):

• Original Constraints.