Sourav (Dada 
) has a very high mathematical aptitude, So he was made the head of the selection committee of Indian Cricket team. There he devised a way to decide whether a player is to be selected or not for the T20 World-Cup.
He collects the data of all the runs scored by a batsmen in the last N innings they played. He then calculates all the possible subsets of the data available.
Now Dada calculates the maximum possible difference(i.e Max - Min) in each subset and adds them. The value generated is termed as BQ(Batting Quotient). He then Calculates BQ for all the T Batsmen. This value will help the committee to decide whether or whether not to select the player.
As you interning under Dada, He has asked you to calculate BQ for all the T Batsmen.
The answer can be very large so, print it modulo 10^9+7.
INPUT
First line of input contains an integer T denoting total number of players.
For each player, first line will contain an integer N denoting number of innings he has played.
Next line contains N space separated integers denoting the runs made in each of the N innings.
OUTPUT
For each player, print a single integer representing the answer of that player.
CONSTRAINS
1<=T<=10
1<=N=10^6
0<=runs<=10^9
LARGE INPUT FAST I/O Preferred
Disclaimer : All the data about runs of batsmen are fictional and has no relation and significance with real life.
For the above case the possible subsets are:
{2} -->2-2 = 0.
{3} --> 3-3 = 0.
{4} --> 4-4 = 0.
{2,3} --> 3-2 = 1.
{2,4} --> 4-2 = 2.
{3,4} --> 4-3 = 1.
{2,3,4} --> 4-2 =2.
So, The BQ will be = 0+0+0+1+2+1+2 = 6.
