Read problems statements in Mandarin Chinese  and Russian. 

Churu is working as a data scientist in Coderpur. He works on a lot of data on the daily basis. One day, he found an interesting problem, which was very easy to solve for small data but was getting more complex with increasing number of data points. So, Churu needs your help in solving this problem.

Given a set S of N non-negative integers (Some integers might occur more than once in the set), find out the value of SETDIFF(S). 

Where max(s) represents the maximum value in set s whereas min(s) represents the minimum value in the set s.
As value of  SETDIFF(S) can be very large, print it modulo  (10^{9} + 7) . 

There might be repeated values in the set. For set S = {1,2,2}, consider that first 2 is not same as the second 2 and there will be two different subsets {1,2}. See last sample case for the more clarifications. 

------ Input ------ 

First line of input contains an integer T denoting number of test cases.  
For each test case, first line will contain an integer N denoting number of elements in set S.  
Next line contains N space separated integers denoting the set S. 

------ Output ------ 

For each test case, print a single integer representing the answer of that test case.

------ Note ------ 

Two subsets will be called different if there exists an index i such that S[i] occurs in one of the subset and not in another.

------ Constraints ------ 

Subtask #1: 20 points

	$1 ≤ T  ≤ 5, 1 ≤ N  ≤ 1000,  0 ≤ value in set ≤ 10^{9}$

Subtask #2: 25 points

	$1 ≤ T  ≤ 5, 1 ≤ N  ≤ 10^{5},  0 ≤ value in set ≤ 1000$

Subtask #3: 55 points

	$1 ≤ T  ≤ 5, 1 ≤ N  ≤ 10^{5},  0 ≤ value in set ≤ 10^{9}$

----- Sample Input 1 ------ 
4

2

1 2

3

1 2 3

4

1 2 3 4

3

1 2 2
----- Sample Output 1 ------ 
1

6 

23

3
----- explanation 1 ------ 

For first case answer will be 2-1 = 1.

For the second case:
Subset = {1}, max(s)-min(s) = 0.
Subset = {2}, max(s)-min(s) = 0.
Subset = {3}, max(s)-min(s) = 0.
Subset = {1,2}, max(s)-min(s) = 1.
Subset = {2,3}, max(s)-min(s) = 1.
Subset = {1,3}, max(s)-min(s) = 2.
Subset = {1,2,3}, max(s)-min(s) = 2.
So the output will be 1+1+2+2 = 6.

In the last case, there are three subsets, {1,2}, {1,2} and {1,2,2} having max(s) - min(s) = 1 for each.

Difficulty: MEDIUM_HARD
Tags: Number theory

Combinatorics

Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	ans = A[-1] - A[0]
	val = 1
	for i in range(len(A) - 2, -1, -1):
		ans += A[i] * (val + 1) % 1000000007
		ans -= A[-i - 1] * (val + 1) % 1000000007
		val = (2 * val + 1) % 1000000007
	print(ans % 1000000007)


def li():
	return list(map(int, input().split()))
	return a

def ii():
	return int(input())
for tastcas in range(int(input())):
	n = ii()
	nn = n - 1
	a = li()
	a.sort()
	mins = maxs = 0
	inf = 1000000007
	for i in range(n):
		mins = (2 * mins + a[i]) % inf
		maxs = (2 * maxs + a[nn - i]) % inf
	print((maxs - mins) % inf)


from math import gcd, sqrt
t = int(input())
mod = 10 ** 9 + 7
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	m1 = 0
	m2 = 0
	for j in range(n):
		m2 += a[j] * pow(2, n - j - 1, mod)
		m2 %= mod
	for k in range(n - 1, -1, -1):
		m1 += a[k] * pow(2, k, mod)
		m1 %= mod
	ans = (m1 - m2) % mod
	print(ans)


p = 1000000000 + 7
power = [1] * (100000 + 1)
for i in range(1, 100000 + 1):
	power[i] = power[i - 1] % p * 2 % p
t = int(input())
while t > 0:
	n = int(input())
	array = list(map(int, input().split()))
	array.sort()
	max_sum = 0
	min_sum = 0
	for i in range(n):
		max_sum += array[i] % p * power[i] % p % p
		min_sum += array[i] % p * power[n - 1 - i] % p % p
	print((max_sum + p - min_sum) % p)
	t -= 1


t = int(input())
for _ in range(t):
	p = 0
	q = 0
	mod = 1000000007
	n = int(input())
	lst = input().split(' ')
	data = [int(i) for i in lst]
	data.sort()
	for i in range(n):
		p = 2 * p + data[i] % mod
		q = 2 * q + data[n - i - 1] % mod
	result = (q - p) % mod
	print(result)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	hash = {}
	p = 0
	q = 0
	m = 10 ** 9 + 7
	l.sort()
	for j in range(n):
		p += pow(2, n - (j + 1), m) * (l[j] % m) % m
		q += pow(2, j, m) * (l[j] % m) % m
	print((q % m - p % m) % m)


e = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	ans = 0
	x = (pow(2, n - 1, e) - 1) % e
	x = x * -1
	c = 1
	d = pow(2, n - 2, e)
	m = pow(2, e - 2, e)
	for i in l:
		ans = (ans + x * i) % e
		x = (x + d + c) % e
		c = c * 2 % e
		d = d * m % e
	print(ans)


t = int(input())
mod = 10 ** 9 + 7
for i in range(t):
	n = int(input())
	n1 = [int(x) for x in input().split()]
	n1.sort()
	(mi, ma) = (0, 0)
	for i in range(n):
		mi = (2 * mi + n1[i]) % mod
		ma = (2 * ma + n1[n - i - 1]) % mod
		di = ma - mi
	print((mod + di) % mod)


m = 10 ** 9 + 7
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	minn = 2 * a[0]
	for i in range(1, n - 1):
		minn += a[i]
		minn *= 2
		minn %= m
	minn += a[n - 1]
	minn %= m
	a.reverse()
	maxx = 2 * a[0]
	for i in range(1, n - 1):
		maxx += a[i]
		maxx *= 2
		maxx %= m
	maxx += a[n - 1]
	maxx %= m
	ans = maxx - minn
	if ans >= 0:
		ans = ans % m
	else:
		while ans < 0:
			ans += m
		ans = ans % m
	print(ans)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	(mini, maxi) = (0, 0)
	for i in range(n):
		mini = (2 * mini + arr[i]) % mod
		maxi = (2 * maxi + arr[n - i - 1]) % mod
	print((mod + maxi - mini) % mod)


(base, mod) = ([1], 1000000007)
for i in range(100005):
	base.append(base[-1] * 2 % mod)
for kase in range(int(input())):
	(_, res, v) = (input(), 0, sorted([int(i) for i in input().split()]))
	for i in range(len(v)):
		res = (res + v[i] * (base[i] - base[len(v) - i - 1])) % mod
	print((res + mod) % mod)


mbase = 1000000007
t = int(input())
for it in range(t):
	n = int(input())
	a = sorted([int(word) for word in input().split()])
	mysum = 0
	pwr2 = 1
	for i in range(n):
		mysum += (a[i] - a[n - 1 - i]) * pwr2
		mysum %= mbase
		pwr2 = pwr2 * 2 % mbase
	print(mysum)


def calc():
	n = int(input())
	a = sorted(map(int, input().split()))
	mod = 1000000007
	x = 0
	y = 0
	for i in range(n):
		x = (2 * x + a[i]) % mod
		y = (2 * y + a[n - i - 1]) % mod
	print((y + mod - x) % mod)
t = int(input())
for i in range(t):
	calc()


T = int(input())
m = 10 ** 9 + 7
b = [1]
for t in range(T):
	N = int(input())
	l = input().split()
	for i in range(N):
		l.append(int(l[i]))
	l = l[N:]
	l.sort()
	i = len(b)
	while i <= N:
		b.append(b[i - 1] * 2 % m)
		i += 1
	sum = 0
	for i in range(N):
		sum += (b[i] - b[N - i - 1]) * l[i]
		if sum > 0:
			sum = sum % m
	print(sum % m)


t = int(input())
pow = [0] * 100002
mod = 1000000007
pow[0] = 1
pow[1] = 2
for j in range(2, 100002, 1):
	pow[j] = pow[j - 1] * 2 % mod
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	for j in range(n):
		ans += a[j] * (pow[j] - pow[n - j - 1])
		if ans > 0:
			ans %= mod
	print(ans % mod)


t = int(input())
m = 1000000007
while t:
	t -= 1
	total = 0
	n = int(input())
	a = list(map(int, input().split()))
	a = sorted(a)
	y = a[n - 1] - a[0]
	i = 1
	j = n - 2
	k = 1
	b = 0
	while b < n - 1:
		total = total + k * y
		y -= a[i] - a[j]
		i += 1
		j -= 1
		k *= 2
		b += 1
		if k > m:
			k = k % m
	print(total % m)


from math import *
t = int(input())
h = [1]
i = 0
y = 10 ** 9 + 7
while i <= 100000:
	h += [h[i] * 2 % y]
	i += 1
for z in range(t):
	n = int(input())
	a = input().split()
	s = []
	for x in a:
		s += [int(x)]
	s.sort()
	v = 0
	for i in range(n):
		v += (-h[n - 1 - i] + h[i]) * s[i]
		v = v % y
	print(v)


from fractions import gcd
t = int(input())
b = [0] * 100000
b[0] = 1
for i in range(1, 100000):
	b[i] = b[i - 1] * 2 % 1000000007
while t > 0:
	n = int(input())
	a = []
	a = [int(x) for x in input().split()]
	r = 0
	a.sort()
	n = len(a)
	for i in range(n // 2):
		r = r + (a[i] - a[n - i - 1]) * (b[i] - b[n - i - 1])
	print(r % 1000000007)
	t = t - 1


t = int(input())
m = 1000000007
po = [1]
ht = 10 ** 5
num = 1
for g in range(1, ht):
	po.append(po[g - 1] * 2 % m)
for j in range(t):
	n = int(input())
	k = input()
	a = list(k.split())
	for y in range(n):
		a[y] = int(a[y])
	a = sorted(a)
	sum = 0
	l = n - 1
	k = 0
	for i in range(n):
		t1 = po[l]
		t2 = po[k]
		sum = (sum + a[i] * t2) % m
		sum = (sum - a[i] * t1) % m
		l = l - 1
		k = k + 1
	print(sum % m)


MOD = 1000000007
power = []
power.append(1)
for i in range(1, 100001):
	power.append(power[i - 1] * 2 % MOD)
t = input()
t = int(t)
while t > 0:
	n = input()
	n = int(n)
	lis = []
	k = input()
	lis = list(k.split())
	for i in range(n):
		lis[i] = int(lis[i])
	SUM = 0
	lis = sorted(lis)
	for i in range(n):
		p = power[i]
		q = power[n - i - 1]
		o = (p - q) % MOD
		k = lis[i] % MOD * o % MOD
		SUM = (SUM % MOD + k) % MOD
	print(SUM)
	t = t - 1


import math
p = int(math.pow(10, 9) + 7)
t = int(input())
twos = [1]
for i in range(t):
	n = int(input())
	if len(twos) < n:
		for i in range(len(twos), n):
			twos.append(int(twos[-1] * 2 % p))
	x = [int(i) for i in input().split()]
	x.sort()
	res = 0
	for i in range(n):
		res += x[i] * (twos[i] - twos[n - 1 - i])
		res = res % p
	if res < 0:
		res += p
	print(res)


import sys

def foo(ns):
	su = 0
	for n in ns:
		su = (su * 2 + n) % 1000000007
	return su
for _ in range(int(sys.stdin.readline())):
	N = int(sys.stdin.readline())
	ns = tuple((int(i) for i in sys.stdin.readline().split()))
	assert N == len(ns)
	ns = sorted(ns)
	print((1000000007 - foo(ns) + foo(reversed(ns))) % 1000000007)


import sys
T = int(sys.stdin.readline())
mod = 10 ** 9 + 7
while T:
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split(' ')))
	A.sort(reverse=True)
	ans = 0
	for (idx, num) in enumerate(A, 1):
		ans = (ans + num * (pow(2, N - idx, mod) - 1) - num * (pow(2, idx - 1, mod) - 1)) % mod
	print(ans)
	T = T - 1


import sys
t = int(sys.stdin.readline())
while t > 0:
	t -= 1
	n = int(sys.stdin.readline())
	a = [int(x) for x in sys.stdin.readline().split()]
	a.sort()
	s = 0
	m = 1
	for i in range(n):
		s = (s + (a[i] - a[n - i - 1]) * m % 1000000007) % 1000000007
		m = (m << 1) % 1000000007
	print(s)


M = 1000000007
N = 100001
p = [0] * N
p[0] = 1
for i in range(1, N):
	p[i] = p[i - 1] * 2
	p[i] %= M
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	s = 0
	for i in range(n):
		s += a[i] * (p[n - i - 1] - p[i])
		s %= M
	print(s)


b1 = [None] * 100005
b1[0] = 1
for i in range(1, 100005):
	b1[i] = 2 * b1[i - 1] % 1000000007
t = int(input())
while t > 0:
	t -= 1
	b = int(input())
	c = input()
	d = [int(n) for n in c.split()]
	d.sort()
	sum = 0
	e = len(d)
	for i in range(1, e):
		sum = sum + (b1[e - i] - 1) * (d[e - i] - d[i - 1])
		sum %= 1000000007
	print(sum)


def heapsort(a):
	length1 = len(a) - 1
	leastParent = int(length1 / 2)
	for i in range(leastParent, -1, -1):
		moveDown(a, i, length1)
	for i in range(length1, 0, -1):
		if a[0] > a[i]:
			swap(a, 0, i)
			moveDown(a, 0, i - 1)

def moveDown(aList, first, last):
	largest1 = 2 * first + 1
	while largest1 <= last:
		if largest1 < last and aList[largest1] < aList[largest1 + 1]:
			largest1 += 1
		if aList[largest1] > aList[first]:
			swap(aList, largest1, first)
			first = largest1
			largest1 = 2 * first + 1
		else:
			return

def swap(A, x, y):
	tmp = A[x]
	A[x] = A[y]
	A[y] = tmp
b1 = [None] * 100005
b1[0] = 1
for i in range(1, 100005):
	b1[i] = 2 * b1[i - 1] % 1000000007
t = int(input())
while t > 0:
	t -= 1
	b = int(input())
	c = input()
	d = [int(n) for n in c.split()]
	d.sort()
	sum = 0
	e = len(d)
	for i in range(1, e):
		sum = sum + (b1[e - i] - 1) * (d[e - i] - d[i - 1])
		sum %= 1000000007
	print(sum)


__author__ = 'huash'
import sys
import os
import random
import datetime
import math
SOLVE2 = False
MOD = 1000000007
POWER2 = [0] * 100000
POWER2[0] = 1
for i in range(1, 100000):
	v = POWER2[i - 1] << 1
	POWER2[i] = v % MOD

def solve1(N, S):
	if len(S) <= 1:
		return 0
	S = sorted(S)
	res = 0
	for l in range(N):
		for r in range(l + 1, N):
			tmp = S[r] - S[l]
			tmp *= pow(2, r - l - 1)
			res = (res + tmp % MOD) % MOD
	return res

def solve2(N, S):
	if len(S) <= 1:
		return 0
	S = sorted(S)
	res = 0
	res = S[0] * ((pow(2, N - 1) - 1) % MOD)
	res %= MOD
	res = -res
	res += S[N - 1] * ((pow(2, N - 1) - 1) % MOD)
	for i in range(1, N - 1):
		v = S[i]
		tmp = 0
		if N - i - 1 < i:
			tmp = S[i] * (pow(2, N - i - 1) % MOD) * ((pow(2, 2 * i - N + 1) - 1) % MOD)
			tmp %= MOD
		elif N - i - 1 > i:
			tmp = S[i] * (pow(2, i) % MOD) * ((pow(2, N - 2 * i - 1) - 1) % MOD)
			tmp = 0 - tmp
		res = (res + tmp) % MOD
	return res

def solve3(N, S):
	if len(S) <= 1:
		return 0
	startTime = datetime.datetime.now()
	smin = min(S)
	smax = max(S)
	bucketSize = int(math.ceil((smax - smin) / (len(set(S)) - 1)))
	buckets = [[] for i in range((smax - smin) // bucketSize + 1)]
	for v in S:
		buckets[(v - smin) // bucketSize].append(v)
	for bucket in buckets:
		bucket.sort()
	partitionTime = datetime.datetime.now() - startTime
	sys.stderr.write('Partition Time:{}\n'.format(partitionTime))
	startTime = datetime.datetime.now()
	res = 0
	res = smin * ((pow(2, N - 1) - 1) % MOD)
	res %= MOD
	res = -res
	res += smax * ((pow(2, N - 1) - 1) % MOD)
	i = -1
	for bucket in buckets:
		for (bi, bv) in enumerate(bucket):
			i += 1
			if i <= 0 or i >= N - 1:
				continue
			tmp = 0
			if N - i - 1 < i:
				tmp = bv * POWER2[N - i - 1] * (POWER2[2 * i - N + 1] - 1)
				tmp %= MOD
			elif N - i - 1 > i:
				tmp = bv * POWER2[i] * (POWER2[N - 2 * i - 1] - 1)
				tmp = 0 - tmp
			res = (res + tmp) % MOD
	calTime = datetime.datetime.now() - startTime
	sys.stderr.write('Calculationg Time:{}, %{}\n'.format(calTime, 100 * calTime / (calTime + partitionTime)))
	return res

def caseGenerator(caseCount, caseSize, maxV, name):
	f = open('input/{}.txt'.format(name), mode='w')
	f.write(str(caseCount))
	f.write('\n')
	for i in range(caseCount):
		N = random.randint(caseSize // 2 + 1, caseSize)
		f.write(str(N))
		f.write('\n')
		sys.stderr.write('Case {}, N={}\n'.format(i + 1, N))
		count = -1
		for j in range(N):
			f.write(str(random.randint(0, maxV)))
			f.write(' ')
			if j - count >= 100:
				count = j
				sys.stderr.write('Generated {}...\n'.format(j + 1))
		f.write('\n')
	sys.stderr.write('Case generate finished')
T = int(input())
for ti in range(1, T + 1):
	N = int(input())
	readStart = datetime.datetime.now()
	S = map(int, input().split())
	sys.stderr.write('Read Cost: {}\n'.format(datetime.datetime.now() - readStart))
	if SOLVE2:
		print(solve2(N, S))
	else:
		res = solve3(N, list(S))
		print(res)
		sys.stderr.write('Time Cose:{}, answer: {}\n'.format(datetime.datetime.now() - readStart, res))


Z = 1000000007

def e(a, b, c):
	x = 1
	while b > 0:
		if b & 1 == 1:
			x = x * a % c
		a = a * a % c
		b >>= 1
	return x % c
t = int(input())
while t:
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	x = [a[n - 1 - i] - a[i] for i in range(n // 2)]
	m = len(x)
	s = 0
	i = 0
	while i < m:
		s = (s + x[i] * ((e(2, n - i - 1, Z) - e(2, i, Z) + Z) % Z) % Z) % Z
		i += 1
	print(s)
	t -= 1


mod = 1000000000 + 7

def modpow(a, n, mod):
	a %= mod
	ans = 1
	while n > 0:
		if n % 2 == 1:
			ans = ans * a % mod
		a = a * a % mod
		n = n >> 1
	return ans
t = int(input())
for test_case in range(t):
	n = int(input())
	nums = sorted([int(x) for x in input().split()])
	ans = 0
	for i in range(n):
		ans += modpow(2, n - i - 1, mod) * ((nums[n - i - 1] - nums[i]) % mod) % mod
		ans = ans % mod
	print(ans)


def solve(l, m):
	n = len(l)
	s = 0
	for i in range(n):
		t = (pow(2, n - i - 1, m) - 1) % m
		if t > 0:
			s += l[n - 1 - i] * t
			s -= l[i] * t
		else:
			break
	print(s % m)
for t in range(int(input())):
	n = int(input())
	data = sorted([int(x) for x in input().split()])
	solve(data, 10 ** 9 + 7)


p = int(1000000000.0 + 7)
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().strip().split()))
	l.sort()
	ans = 0
	for i in range(n):
		ans += l[i] * (pow(2, i, p) - pow(2, n - i - 1, p))
		ans %= p
	print(ans)