game-of-strengths-4

Andrew is very fond of Maths.He has N boxes with him,in each box there is some value which represents the Strength of the Box.The ith box has strength A[i].
He wants to calculate the Overall Power of the all N Boxes.

Overall Power here means Sum of Absolute Difference of the strengths of the boxes(between each pair of boxes) multiplied by the Maximum strength among N boxes.
Since the Overall Power could be a very large number,output the number modulus 10^9+7(1000000007).

Input

First line of the input contains the number of test cases T.  It is followed by T test cases.
Each test case has 2 lines. First line contains the number of boxes N. It is followed by a line containing N elements where ith element is the strength of Andrew's ith box.

Output

For each test case, output a single number, which is the Overall Power for that testcase.

Constraints

1 ≤ T ≤ 10

2 ≤ N ≤ 10^5

0 ≤ A[i] ≤ 10^9

SAMPLE INPUT
2
2
1 2
5
4 5 3 1 2

SAMPLE OUTPUT
2
100

Explanation

For 1st test case sum of absolute difference between strength  is 1.So Overall Power would be 2.

For 2nd test case sum of absolute difference between each pair of boxes is 20.So Overall Power is 100.

Source: hackerearth | Difficulty: EASY
Tags: Sorting

Mathematics


Solutions:
t=eval(input())
while t>0:
	sum=0
	n=eval(input())
	a=list(map(int,input().split()))
	a.sort(reverse=True)
	for i in range(1,n):
		sum+=a[0]-a[i]
	temp1=sum
	for i in range (1,n-1):
		temp=temp1-(n-i)*(a[i-1]-a[i])
		sum=(sum+temp) 
		temp1=temp
	sum=sum%1000000007
	x=(sum*a[0])%1000000007
	print(x)
	t-=1


t=eval(input())
while t>0:
	sum=0
	n=eval(input())
	a=list(map(int,input().split()))
	a.sort(reverse=True)
	for i in range(1,n):
		sum+=a[0]-a[i]
	temp1=sum
	for i in range (1,n-1):
		temp=temp1-(n-i)*(a[i-1]-a[i])
		sum=(sum+temp) 
		temp1=temp
	sum=sum%1000000007
	y=(sum*a[0])%1000000007
	print(y)
	t-=1


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
'''binary-indexed tree, allows point updates and prefix sum queries
Copied the code for calculating the absolute difference from  : http://stackoverflow.com/questions/22943787/sum-of-absolute-differences-of-a-number-in-an-array
'''
class Fenwick:
	def __init__(self, n):
		self.tree = [0]*(n+1)
		self.n = n
	def update_point(self, i, val):  # O(log n)
		i += 1
		while i <= self.n:
			self.tree[i] += val
			i += i & -i
	def read_prefix(self, i):        # O(log n)
		i += 1
		sum = 0
		while i > 0:
			sum += self.tree[i]
			i -= i & -i
		return sum

def solve(a):
	rank = { v : i for i, v in enumerate(sorted(a)) }
	res = []
	counts, sums = Fenwick(len(a)), Fenwick(len(a))
	total_sum = 0
	for i, x in enumerate(a):
		r = rank[x]
		num_smaller = counts.read_prefix(r)
		sum_smaller = sums.read_prefix(r)
		res.append(total_sum - 2*sum_smaller + x * (2*num_smaller - i))
		counts.update_point(r, 1)
		sums.update_point(r, x)
		total_sum += x
	return res


N = int(input())
i = 0
while i < N:
		count = input()
		x = input().split()
		new_x = [int(j) for j in x]
		res = sum(solve(new_x)) * max(new_x)
		if(res > 1000000007):
			res = res % 1000000007
		print(res)
		i = i + 1


for i in range(int(input())):
	n = eval(input())-1
	a = [int(j) for j in input().split()]
	a.sort(reverse=True)
	
	sum1=0
	for i in a:
		prod = n*i
		sum1 += prod
		n-=2
	print((sum1*a[0])%(10**9+7))


T= int(input())
for q in range(T):
	N= int(input())
	ST= input()
	ST= ST.split()
	d=0
	S = [int(i) for i in ST]
	S=sorted(S, key=int, reverse=True) 
	for z in range(N):
		d=d+(N-1-(2*z))*S[z]	
	m=max(S)
	s= int(d)* int(m)
	print(s%1000000007)
	


t=int(input())
for j in range (0,t):
	sum=0
	num=int(input())
	arr=list(map(int,input().split()))
	arr.sort(reverse=True)
	for i in range(1,num):
		sum+=arr[0]-arr[i]
	temp1=sum
	for i in range(1,num-1):
		temp=temp1-(num-i)*(arr[i-1]-arr[i])
		sum=(sum+temp) 
		temp1=temp
	sum=sum%1000000007
	y=(sum*arr[0])%1000000007
	print(y)


times=eval(input())

while times>0:
	n=eval(input())
	ans=0
	arr = [int(x) for x in input().split()]
	arr.sort(reverse = True)
	for i in range(0, n/2):
		ans = ans + ((n-1-2*i)*(arr[i]-arr[n-i-1]));

	ans = (ans*arr[0])%1000000007
	print(ans)
	times = times-1


t=eval(input())
while t>0:
	sum=0
	n=eval(input())
	a=list(map(int,input().split()))
	a.sort(reverse=True)
	for i in range(1,n):
		sum+=a[0]-a[i]
	temp1=sum
	for i in range (1,n-1):
		temp=temp1-(n-i)*(a[i-1]-a[i])
		sum=(sum+temp) 
		temp1=temp
	sum=sum%1000000007
	y=(sum*a[0])%1000000007
	print(y)
	t-=1


#!/usr/bin/env python
#-*- coding: utf-8 -*-

from collections import defaultdict
from math import factorial as f
MOS = 10 ** 9 + 7

T = int (input ())
for t in range (T):
	n = int (input ())
	l = [int (i) for i in input ().split ()]
	ret = 0
	l.sort (reverse = True)
	N = len (l)
	p = N - 1
	for i in range (len (l)):
		#print ret
		ret += (p * l [i])
		p -= 2
	print((ret * max (l)) % (10**9 + 7))



t=int(input())
for asfas in range(t):
	n=int(input())
	arr=[int(e) for e in input().split()]
	arr.sort()
	b=[0]*n
	c=[0]*n
	ab=0
	for i in range(1,n):
		b[i]=b[i-1]+arr[i-1]
		c[n-i-1]=c[n-i]+arr[n-i]
		ab=ab-(b[i]-arr[i]*i) + (c[n-i-1]-arr[n-i-1]*i)
	ab/=2
	print((ab*max(arr))%1000000007)
		


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
'''binary-indexed tree, allows point updates and prefix sum queries
Copied from : http://stackoverflow.com/questions/22943787/sum-of-absolute-differences-of-a-number-in-an-array
'''
class Fenwick:
	def __init__(self, n):
		self.tree = [0]*(n+1)
		self.n = n
	def update_point(self, i, val):  # O(log n)
		i += 1
		while i <= self.n:
			self.tree[i] += val
			i += i & -i
	def read_prefix(self, i):        # O(log n)
		i += 1
		sum = 0
		while i > 0:
			sum += self.tree[i]
			i -= i & -i
		return sum

def solve(a):
	rank = { v : i for i, v in enumerate(sorted(a)) }
	res = []
	counts, sums = Fenwick(len(a)), Fenwick(len(a))
	total_sum = 0
	for i, x in enumerate(a):
		r = rank[x]
		num_smaller = counts.read_prefix(r)
		sum_smaller = sums.read_prefix(r)
		res.append(total_sum - 2*sum_smaller + x * (2*num_smaller - i))
		counts.update_point(r, 1)
		sums.update_point(r, x)
		total_sum += x
	return res


N = int(input())
i = 0
while i < N:
		count = input()
		x = input().split()
		new_x = [int(j) for j in x]
		res = sum(solve(new_x)) * max(new_x)
		if(res > 1000000007):
			res = res % 1000000007
		print(res)
		i = i + 1


tc = int(input())
MOD = 1000000007
while tc:
	n = int(input())
	nos = (input()).split()
	nos = [int(p) for p in nos]
	nos.sort()
	summ = 0
	for i in range(n):
		summ += (nos[i]*i - nos[i]*(n-i-1))

	print((summ*max(nos))%MOD)
	tc-=1



m=(10**9)+7
for _ in range(eval(input())):
	n=eval(input())
	x=sorted(map(int,input().split()))
	p=n-1
	s=0
	for i in range(n-1,-1,-1):
	#	print x[i],p
		s+=p*x[i]
		p-=2
	print((s*x[n-1])%m)


t=eval(input())
while t>0:
	sum=0
	n=eval(input())
	a=list(map(int,input().split()))
	a.sort(reverse=True)
	for i in range(1,n):
		sum+=a[0]-a[i]
	temp1=sum
	for i in range (1,n-1):
		temp=temp1-(n-i)*(a[i-1]-a[i])
		sum=(sum+temp) 
		temp1=temp
	sum=sum%1000000007
	x=(sum*a[0])%1000000007
	print(x)
	t-=1


T = int(input())
for t in range(T):
	N = int(input())
	inp = input().split(' ') 
	strengths=[]
	for n in range(N):
		strengths.append(int(inp[n]))
	
	strengths.sort()
	sumofstrengths = 0
	total=0
	for num in strengths:
		total = total + num
	
	for i in range(N):
		total = total - strengths[i]
		sumofstrengths= sumofstrengths + total  - ( (N-i-1) * strengths[i] )
	
	maxs = strengths.pop()
	absolutepower = sumofstrengths * maxs
	print(absolutepower%1000000007)


def main():
	s = raw_input
	t = int(s())
	for test in range(t):
		n = int(s())
		arr = list(map(int, s().split()))
		arr.sort()
		x, y = 0, 0
		for i in range(1, n):
			x = (((arr[i]-arr[i-1])*(i)) + x)%1000000007
			y += x
		print(((y*arr[n-1])%1000000007))

main()



def AbsDiff(a,n):
	if ( n < 2 ) :
		return 0  
	Sum = 0
	for i in range(n-1,-1,-1):
		Sum+= (a[i]*(i) - a[i]*(n-i-1))
		m=Sum%1000000007
	return Sum%1000000007;

t=int(input())
while(t):
	n=int(input())
	Sum=0
	boxes=list(map(int,input().split()))
	boxes.sort()
	result=(AbsDiff(boxes,n)*max(boxes))%1000000007
	print(result)
	t-=1


m = (10**9)+7;
for i in range(int(input())):
	n = int(input())
	num = sorted(map(int,input().split()));
	maxnum = num[n-1];
	productconstant = n-1;
	abssum = 0;
	for j in range(n-1,-1,-1):
		abssum+=(num[j]*productconstant);
		productconstant-=2;
	print((abssum*maxnum)%m);