Maximum Sum

Ninja likes rearranging arrays. This time he rearranges the array ‘A’ of size ‘N’ such that the sum of ‘A[i]*i’ over all indices is maximized.

Output the maximum sum achievable after rearranging the array ‘A’. Assume 0-based indexing. Since the answer can be large, output it modulo 10^9+7.

Example :

N = 3
A = [ 1, 2, 1 ]

Explanation : 

The rearrangements of array ‘A’ can be [ 1, 1, 2] , [ 1, 2, 1] and [ 2, 1, 1].
The sum for [ 1, 1, 2 ] is 0*1 + 1*1 + 2*2 = 5.
The sum for [ 1, 2, 1 ] is 0*1 + 1*2 + 2*1 = 4.
The sum for [ 2, 1, 1 ] is 0*2 + 1*1 + 2*1 = 3.
The maximum among these is 3.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains an integer ‘N’.

The next line contains ‘N’ integers representing the elements of array ‘A’ .

Output format :

For each test case, output an integer denoting the maximum sum.

Print the output of each test case in a new line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
2 <= N <= 10^5
1 <= A[i] <= 10^5

Time Limit : 1 sec