Leha decided to move to a quiet town Vičkopolis, because he was tired by living in Bankopolis. Upon arrival he immediately began to expand his network of hacked computers. During the week Leha managed to get access to n computers throughout the town. Incidentally all the computers, which were hacked by Leha, lie on the same straight line, due to the reason that there is the only one straight street in Vičkopolis.

Let's denote the coordinate system on this street. Besides let's number all the hacked computers with integers from 1 to n. So the i-th hacked computer is located at the point x_{i}. Moreover the coordinates of all computers are distinct. 

Leha is determined to have a little rest after a hard week. Therefore he is going to invite his friend Noora to a restaurant. However the girl agrees to go on a date with the only one condition: Leha have to solve a simple task.

Leha should calculate a sum of F(a) for all a, where a is a non-empty subset of the set, that consists of all hacked computers. Formally, let's denote A the set of all integers from 1 to n. Noora asks the hacker to find value of the expression $\sum_{a \subseteq A, a \neq \varnothing} F(a)$. Here F(a) is calculated as the maximum among the distances between all pairs of computers from the set a. Formally, $F(a) = \operatorname{max}_{i, j \in a}|x_{i} - x_{j}|$. Since the required sum can be quite large Noora asks to find it modulo 10^9 + 7.

Though, Leha is too tired. Consequently he is not able to solve this task. Help the hacker to attend a date.


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 3·10^5) denoting the number of hacked computers.

The second line contains n integers x_1, x_2, ..., x_{n} (1 ≤ x_{i} ≤ 10^9) denoting the coordinates of hacked computers. It is guaranteed that all x_{i} are distinct.


-----Output-----

Print a single integer — the required sum modulo 10^9 + 7.


-----Examples-----
Input
2
4 7

Output
3

Input
3
4 3 1

Output
9



-----Note-----

There are three non-empty subsets in the first sample test:$\{4 \}$, $\{7 \}$ and $\{4,7 \}$. The first and the second subset increase the sum by 0 and the third subset increases the sum by 7 - 4 = 3. In total the answer is 0 + 0 + 3 = 3.

There are seven non-empty subsets in the second sample test. Among them only the following subsets increase the answer: $\{4,3 \}$, $\{4,1 \}$, $\{3,1 \}$, $\{4,3,1 \}$. In total the sum is (4 - 3) + (4 - 1) + (3 - 1) + (4 - 1) = 9.

Source: codeforces | Difficulty: MEDIUM
Tags: Mathematics

Sorting

Implementation


Solutions:
(n, ans, m, s) = (int(input()), 0, 1000000007, [0])
a = sorted(map(int, input().split()))
for i in range(1, n):
	s.append((2 * s[i - 1] + a[i - 1]) % m)
	ans += ((pow(2, i, m) - 1) * a[i] - s[i]) % m
print(ans % m)


n = int(input())
R = lambda : map(int, input().split())
l = list(R())
l.sort()
(s, m) = (0, 1000000007)
for i in range(n):
	s = (s + l[i] * (pow(2, i, m) - pow(2, n - 1 - i, m))) % m
print(s)


import sys, math, itertools, collections, bisect
input = lambda : sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
mod = 10 ** 9 + 7
mans = inf
ans = 0
count = 0
pro = 1
n = int(input())
A = list(map(int, input().split()))
A.sort()
for i in range(n):
	ans -= pow(2, n - i - 1, mod) * A[i]
	ans += pow(2, i, mod) * A[i]
ans %= mod
print(ans)


n = int(input())
inf = 10 ** 9 + 7
a = list(map(int, input().split()))
st = [0 for i in range(n)]
st[0] = 1
for i in range(1, n):
	st[i] = st[i - 1] * 2 % inf
a.sort()
res = 0
for i in range(n - 1):
	res += (a[i + 1] - a[i]) * (st[i + 1] - 1) * (st[n - i - 1] - 1)
	res %= inf
print(res)


from sys import stdin, stdout
n = int(stdin.readline())
values = sorted(list(map(int, stdin.readline().split())))
MOD = 10 ** 9 + 7
dp = [0]
cnt = [values[0]]
pw = [1]
for i in range(n):
	pw.append(pw[-1] * 2 % MOD)
for i in range(1, n):
	dp.append((dp[-1] + values[i] * (pw[i] - 1) - cnt[-1]) % MOD)
	cnt.append(cnt[-1] * 2 + values[i])
	cnt[-1] %= MOD
stdout.write(str(dp[-1] % MOD))


n = int(input())
l = list(map(int, input().strip().split(' ')))
p = 1
l.sort()
length = len(l)
ans = 0
for i in range(len(l)):
	ans += p * (l[i] - l[length - i - 1])
	p *= 2
	p %= 1000000007
	ans %= 1000000007
print(int(ans))


n = int(input())
x = list(map(int, input().split()))
x.sort()
ans = 0
for i in range(n):
	ans += (pow(2, i, 1000000007) - pow(2, n - i - 1, 1000000007)) * x[i] % 1000000007
	ans = ans % 1000000007
print(ans)


def main():
	mod = 10 ** 9 + 7
	pws = [None for i in range(4 * 10 ** 5)]
	pws[0] = 1
	for i in range(1, 4 * 10 ** 5):
		pws[i] = 2 * pws[i - 1] % mod
	n = int(input())
	seq = list(map(int, input().split()))
	seq.sort()
	ans = 0
	for i in range(n):
		ans += seq[i] * (pws[i] - 1)
		ans -= seq[i] * (pws[n - i - 1] - 1)
		ans = ans % mod
	print(ans)
main()


def main():
	largemodulus = 1000000007
	maxofn = 300001
	n = 0
	answer = 0
	powersoftwo = []
	multiplier = 1
	for _ in range(maxofn):
		powersoftwo.append(multiplier)
		if multiplier >= largemodulus:
			multiplier = multiplier % largemodulus
		multiplier *= 2
	n = int(input())
	hacked = [int(i) for i in input().split()]
	hacked.sort(reverse=True)
	for x in range(n):
		answer += hacked[x] * (powersoftwo[n - 1 - x] - 1 - (powersoftwo[x] - 1)) % largemodulus
		if answer >= largemodulus:
			answer = answer % largemodulus
	print(answer)
	return
main()


import os
import sys
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 10 ** 9 + 7
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
n = Int()
a = sorted(array())
ans = 0
l = 0
r = n - 1
for i in a:
	high = pow(2, l, M)
	low = pow(2, r, M)
	l += 1
	r -= 1
	ans = (ans + high * i % M) % M
	ans = (M + ans - low * i % M) % M
print(ans)


def rint():
	return int(input())

def rints():
	return list(map(int, input().split()))
MOD = 10 ** 9 + 7
n = rint()
x = rints()
x.sort()
s = 0
for i in range(1, n):
	s += (x[i] - x[i - 1]) * (pow(2, i, MOD) - 1) * (pow(2, n - i, MOD) - 1) % MOD
	s %= MOD
print(s)


import sys
import math
MOD = int(1000000000.0 + 7)
line = lambda : map(int, input().split())

def solve():
	n = int(input())
	x = [x for x in line()]
	x.sort()
	p2 = []
	p2.append(1)
	for i in range(1, n):
		p2.append(p2[i - 1] * 2 % MOD)
	ans = 0
	for i in range(n):
		ans += x[i] * (p2[i] - p2[n - i - 1] + MOD)
		ans %= MOD
	print(ans)

def main():
	solve()
	exit(0)
main()


import sys
from itertools import accumulate
n = int(input())
if n == 1:
	print(0)
	sys.exit()
d = [int(x) for x in input().split()]
d.sort()
mod = 10 ** 9 + 7

def add_mod(x, y):
	return (x + y) % mod
p2 = [1 for i in range(n)]
p2_inv = [1 for i in range(n)]
p2[1] = 2
p2_inv[0] = pow(p2[1], mod - 2, mod)
p2_inv[1] = pow(p2_inv[0], 2, mod)
for i in range(2, n):
	p2[i] = p2[i - 1] * 2 % mod
	p2_inv[i] = p2_inv[i - 1] * p2_inv[0] % mod
p2_suf = list(accumulate(reversed(p2), func=add_mod))
p2_suf.reverse()
z_suf = list(accumulate(reversed([d[i] * p2[i] for i in range(n)]), func=add_mod))
z_suf.reverse()
ans = 0
for i in range(n - 1):
	cur = z_suf[i + 1] - d[i] * p2_suf[i + 1] % mod
	if cur < 0:
		cur += mod
	cur = cur * p2_inv[i] % mod
	ans += cur
	if ans > mod:
		ans -= mod
print(ans)


n = int(input())
a = sorted(list(map(int, input().split())))
base = 10 ** 9 + 7
d = [1]
for i in range(n):
	d.append(2 * d[-1] % base)
ans = 0
for i in range(1, len(a)):
	diff = a[i] - a[i - 1]
	add = diff * (d[i] - 1) * (d[n - i] - 1) % base
	ans += add
	ans = ans % base
print(ans)


import sys
mod = 10 ** 9 + 7

def solve():
	n = int(input())
	x = [int(i) for i in input().split()]
	x.sort()
	ans = 0
	p2 = [1] * (n + 1)
	for i in range(1, n + 1):
		p2[i] = 2 * p2[i - 1] % mod
	for i in range(n):
		ans += x[i] * (p2[i] - p2[n - 1 - i]) % mod
		ans %= mod
	print(ans)
solve()


mod = 10 ** 9 + 7
n = int(input())
x = sorted(list(map(int, input().split())))
total = 0
for (i, (a, b)) in enumerate(zip(x, x[1:])):
	diff = b - a
	total += (pow(2, i + 1, mod) - 1) * (pow(2, n - i - 1, mod) - 1) * diff
	total %= mod
print(total)


n = int(input())
a = list(map(int, input().split()))
m = 1000000007
s = 0
a.sort()
for i in range(n):
	s = (s + a[i] * (pow(2, i, m) - pow(2, n - 1 - i, m))) % m
print(s)


n = int(input())
A = list(map(int, input().split()))
A = sorted(A)
M = 10 ** 9 + 7
pw = [1]
(sumF, sumL) = (0, 0)
for i in range(n - 1):
	pw.append(2 * pw[i] % M)
for i in range(n):
	sumF = (sumF + A[i] * pw[n - 1 - i]) % M
for i in range(n):
	sumL = (sumL + A[i] * pw[i]) % M
print((sumL - sumF + M) % M)


N = 10 ** 9 + 7
n = int(input())
x = sorted(list(map(int, input().split())))
p2n = []
a = 1
for _ in range(n + 1):
	p2n.append(a)
	a = a * 2 % N
ret = 0
for i in range(n - 1):
	ret = (ret + (x[i + 1] - x[i]) * (p2n[i + 1] - 1) * (p2n[n - i - 1] - 1)) % N
print(ret)


n = int(input())
a = sorted(list(map(int, input().split())))
if n == 1:
	print(0)
	exit(0)
f = a[1] - a[0]
deg = 2
ans = f
MOD = int(10 ** 9 + 7)
for i in range(2, n):
	d = a[i] - a[i - 1]
	f = (2 * (f % MOD + (deg % MOD - 1) % MOD * (d % MOD) % MOD) + d % MOD) % MOD
	ans = (f % MOD + ans % MOD) % MOD
	deg *= 2
	deg %= MOD
print(ans % MOD)


n = int(input())
coord = [int(x) for x in input().split()]
coord = sorted(coord)
modul = 1000000007
G = [0]
P = [0]
D = [0]
for i in range(1, n + 1):
	gi = (G[i - 1] * 2 + coord[i - 1]) % modul
	pi = (2 * P[i - 1] + 1) % modul
	G.append(gi)
	P.append(pi)
for i in range(1, n):
	di = (D[i - 1] + P[i] * coord[i] - G[i]) % modul
	D.append(di)
print(D[n - 1])


import sys
n = int(input())
if n == 1:
	print(0)
	sys.exit()
d = [int(x) for x in input().split()]
d.sort()
mod = 10 ** 9 + 7
p2 = [1 for i in range(n)]
p2_inv = [1 for i in range(n)]
p2[1] = 2
p2_inv[0] = pow(p2[1], mod - 2, mod)
p2_inv[1] = pow(p2_inv[0], 2, mod)
for i in range(2, n):
	p2[i] = p2[i - 1] * 2 % mod
	p2_inv[i] = p2_inv[i - 1] * p2_inv[0] % mod
p2_suf = p2[:]
for i in range(n - 2, -1, -1):
	p2_suf[i] += p2_suf[i + 1]
	if p2_suf[i] >= mod:
		p2_suf[i] -= mod
z = [0 for i in range(n)]
for i in range(n):
	z[i] = d[i] * p2[i] % mod
z_suf = z[:]
for i in range(n - 2, -1, -1):
	z_suf[i] += z_suf[i + 1]
	if z_suf[i] >= mod:
		z_suf[i] -= mod
ans = 0
for i in range(n - 1):
	cur = z_suf[i + 1] - d[i] * p2_suf[i + 1] % mod
	if cur < 0:
		cur += mod
	cur = cur * p2_inv[i] % mod
	ans += cur
	if ans > mod:
		ans -= mod
print(ans)


maxn = 300005
mod = 1000000007
n = int(input())
(ans, temp) = (0, 0)
a = [0] * maxn
b = [0] * maxn
b[0] = 1
for i in range(1, maxn):
	b[i] = 2 * b[i - 1]
	if b[i] >= mod:
		b[i] -= mod
k = 1
for i in input().split():
	a[k] = int(i)
	k += 1
a[1:n + 1] = sorted(a[1:n + 1])
for i in range(1, n + 1):
	temp = a[i] * (b[i - 1] - b[n - i])
	if temp >= 0:
		temp %= mod
	else:
		temp *= -1
		temp %= mod
		temp = mod - temp
	ans += temp
	if ans >= mod:
		ans -= mod
print(ans)


N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
s = 0
M = 1000000007
for i in range(N):
	s += A[i] * (pow(2, N - i - 1, M) - pow(2, i, M))
	s %= M
print(s)


(R, n, x, p, v) = (10 ** 9 + 7, int(input()), sorted(map(int, input().split())), [1], 0)
for i in range(1, n):
	p.append(2 * p[-1] % R)
print(sum(((x[i] - x[i - 1]) * (p[i] - 1) * (p[n - i] - 1) for i in range(1, n))) % R)


n = int(input())
x = list(map(int, input().split()))
MOD = 10 ** 9 + 7
x.sort()
diff = []
for i in range(1, n):
	diff.append(x[i] - x[i - 1])
tot = 0
totSide = 0
po = 1
poSum = 0
for d in diff:
	poSum += po
	poSum %= MOD
	totSide *= 2
	totSide += d * poSum
	totSide %= MOD
	tot += totSide
	tot %= MOD
	po *= 2
	po %= MOD
print(tot)


M = 1000000007
n = int(input())
x = list(map(int, input().split(' ')))
x = sorted(x)
res = 0
pow2 = 0
for i in range(n):
	res += pow2 * x[i]
	res -= pow2 * x[n - 1 - i]
	pow2 = (pow2 * 2 + 1) % M
	res = res % M
print(res)


import sys
input = sys.stdin.readline
n = int(input())
x = list(map(int, input().split()))
x.sort()
ans = 0
MOD = 10 ** 9 + 7
for i in range(n - 1):
	d = x[i + 1] - x[i]
	l = pow(2, i + 1, MOD) - 1
	r = pow(2, n - i - 1, MOD) - 1
	ans += d * l * r
	ans %= MOD
print(ans)


n = int(input())
li = list(map(int, input().split()))
modulo = 1000000007
temp = 0
res = 0
counter = 2
li.sort()
for i in range(1, n):
	temp = 2 * temp % modulo + (li[i] - li[i - 1]) * ((counter - 1) % modulo)
	res = (res + temp) % modulo
	counter = (counter << 1) % modulo
print(res)


(n, x) = (int(input()), list(sorted(list(map(int, input().split())))))
kk = 1
a = 0
for i in range(len(x)):
	a += (x[i] - x[len(x) - i - 1]) * kk
	kk *= 2
	kk %= 1000000007
	a %= 1000000007
print(a)


mod = 10 ** 9 + 7

def power(a, b):
	r = 1
	a %= mod
	while b:
		if b & 1:
			r = r % mod * (a % mod) % mod
		a = a % mod * (a % mod) % mod
		b >>= 1
	return r % mod
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
res = 0
k = 0
for i in arr:
	res -= i * power(2, n - k - 1) % mod
	res += i * power(2, k) % mod
	k += 1
print(res % mod)


mod = int(1000000000.0 + 7)
n = int(input())
a = input()
b = list(map(int, a.strip().split()))
b.sort()
c = []
next = 1
for i in range(n):
	c.append(next)
	next = next * 2 % mod
ans = 0
for i in range(n):
	ans = (ans - b[i] * (c[n - i - 1] - 1) % mod + mod) % mod
	ans = (ans + b[i] * (c[i] - 1) % mod) % mod
print(ans)


MOD = int(1000000000.0 + 7)
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
l = 1
r = 0
for i in range(n):
	r = (r + l * arr[i]) % MOD
	l = l * 2 % MOD
l = 1
for i in range(n - 1, -1, -1):
	r = (r - l * arr[i]) % MOD
	l = l * 2 % MOD
print(r)


import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def lcm(x, y):
	return x * y / gcd(x, y)

def fact(x, mod=mod):
	ans = 1
	for i in range(1, x + 1):
		ans = ans * i % mod
	return ans

def arr2D(n, m, default=0):
	return [[default for j in range(m)] for i in range(n)]

def arr3D(n, m, r, default=0):
	return [[[default for k in range(r)] for j in range(m)] for i in range(n)]

def sortDictV(x):
	return {k: v for (k, v) in sorted(x.items(), key=lambda item: item[1])}

class DSU:

	def __init__(self, length):
		self.length = length
		self.parent = [-1] * self.length

	def getParent(self, node, start):
		if node >= self.length:
			return False
		if self.parent[node] < 0:
			if start != node:
				self.parent[start] = node
			return node
		return self.getParent(self.parent[node], start)

	def union(self, node1, node2):
		parent1 = self.getParent(node1, node1)
		parent2 = self.getParent(node2, node2)
		if parent1 == parent2:
			return False
		elif self.parent[parent1] <= self.parent[parent2]:
			self.parent[parent1] += self.parent[parent2]
			self.parent[parent2] = parent1
		else:
			self.parent[parent2] += self.parent[parent1]
			self.parent[parent1] = parent2
		return True

	def getCount(self, node):
		return -self.parent[self.getParent(node, node)]

def exact(num):
	if abs(num - round(num)) <= 10 ** (-9):
		return round(num)
	return num
MOD = 1000000007

def maxMin(arr, n):
	arr.sort()
	min_sum = 0
	max_sum = 0
	for i in range(0, n):
		max_sum = 2 * max_sum + arr[n - 1 - i]
		max_sum %= MOD
		min_sum = 2 * min_sum + arr[i]
		min_sum %= MOD
	return (max_sum - min_sum + MOD) % MOD
n = int(input())
arr = list(map(int, input().split()))
print(maxMin(arr, n))


import sys

def solution():
	MOD = int(1000000000.0 + 7)
	n = int(input())
	x = list(map(int, sys.stdin.readline().split()))
	x.sort(reverse=True)
	ac1 = [x[0]]
	for i in range(1, len(x)):
		ac1.append((ac1[-1] + x[i]) % MOD)
	x = x[::-1]
	ac2 = [x[0]]
	for i in range(1, len(x)):
		ac2.append((ac2[-1] + x[i]) % MOD)
	ans = 0
	lim = n // 2
	for i in range(lim):
		ans = (ans + pow(2, i, MOD) * (ac1[i] - ac2[i] + MOD) % MOD) % MOD
	if n % 2 == 0:
		lim -= 1
	for i in range(lim):
		ans = (ans + (pow(2, n - 2 - i, MOD) * (ac1[i] - ac2[i]) + MOD) % MOD) % MOD
	print(ans)
solution()


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


import sys
read = lambda : sys.stdin.readline().rstrip()
readi = lambda : int(sys.stdin.readline())
writeln = lambda x: sys.stdout.write(str(x) + '\n')
write = lambda x: sys.stdout.write(x)
MOD = 10 ** 9 + 7
N = readi()
ns = list(map(int, read().split()))
ns.sort()
s = 0
powmod = 1
ps = [0] * N
ps[0] = 1
for i in range(1, N):
	ps[i] = 2 * ps[i - 1] % MOD
for i in range(N):
	s += ns[i] * ps[i]
	s -= ns[i] * ps[-1 - i]
	s %= MOD
writeln(s)


n = int(input())
l = [int(i) for i in input().split()]
sm = 0
MOD = 10 ** 9 + 7
add = 0
sub = 0
l.sort()
p = 3 * 10 ** 5 + 9
pow2 = [0] * p
pow2[0] = 1
for i in range(1, p):
	pow2[i] = pow2[i - 1] * 2 % MOD
for i in range(n):
	add += l[i] * pow2[i]
	sub += l[i] * pow2[n - i - 1]
print((add - sub + MOD) % MOD)


n = int(input())
ar = list(map(int, input().split()))
ar.sort()
MOD = 10 ** 9 + 7
ans = 0
for i in range(n):
	bef = i
	aft = n - i - 1
	if bef < aft:
		ans -= ar[i] * (pow(2, aft, MOD) - pow(2, bef, MOD) + MOD) % MOD
		ans %= MOD
	elif aft < bef:
		ans += ar[i] * (pow(2, bef, MOD) - pow(2, aft, MOD) + MOD) % MOD
		ans %= MOD
print(ans)


n = int(input())
a = sorted(list(map(int, input().split())))
modu = 10 ** 9 + 7
if n < 2:
	print(0)
else:
	ans = 0
	p2 = [1]
	for i in range(n):
		p2.append(2 * p2[-1] % modu)
	for i in range(n - 1):
		ans += (a[i + 1] - a[i]) * (p2[i + 1] - 1) * (p2[n - i - 1] - 1)
		ans %= modu
	print(ans)


n = int(input())
a = list(map(int, input().split(' ')))
a.sort()
p = 10 ** 9 + 7
ans = 0
two = 1
for x in a:
	ans += two * x
	two = two * 2 % p
a = reversed(a)
two = 1
for x in a:
	ans -= two * x
	two = two * 2 % p
ans = ans % p
print(ans)


import math as mt
import sys, string, bisect
input = sys.stdin.readline
import random
from collections import deque, defaultdict
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
d = defaultdict(int)
f = defaultdict(int)
n = I()
m = 10 ** 9 + 7
l = L()
l.sort(reverse=True)
s = 0
for i in range(n):
	s += l[i] * pow(2, n - (i + 1), m)
	s -= l[i] * pow(2, i, m)
print(s % m)


inf = 1000000007
n = int(input())
a = list(map(int, input().split()))
a.sort()
(ans, st2) = (0, 0)
for i in range(n):
	ans += st2 * a[i] - st2 * a[n - i - 1]
	st2 = (st2 * 2 + 1) % inf
print(ans % inf)


n = int(input())
V = list(map(int, input().split()))
V.sort()
Mod = int(1000000000.0 + 7)
Sum = 0
p = [1]
for i in range(n):
	p.append(p[i] * 2 % Mod)
for i in range(n - 1):
	l = (p[i + 1] + Mod - 1) % Mod
	r = (p[n - i - 1] - 1 + Mod) % Mod
	Sum = (Sum + (V[i + 1] - V[i]) * l * r) % Mod
print(int(Sum))


n = int(input())
ans = 0
MOD = int(10 ** 9 + 7)
a = [int(x) for x in input().split()]
a.sort()
po = [1]
for i in range(1, n):
	po.append(po[i - 1] * 2 % MOD)
for i in range(n):
	ans += a[i] * (po[i] - po[n - i - 1] + MOD)
	ans %= MOD
print(ans)


n = int(input())
arr = sorted(list(map(int, input().split())))
res = 0
mod = 1000000007
acc = 0
arr = [arr[i + 1] - arr[i] for i in range(n - 1)]
n -= 1
s = sum(arr)
for i in range((n + 1) // 2):
	acc += s
	res += acc * pow(2, n - i - 1, mod) % mod
	if not i * 2 + 1 == n:
		res += acc * pow(2, i, mod) % mod
	res %= mod
	s -= arr[i] + arr[n - i - 1]
print(res)


N = int(input())
X = list(map(int, input().split()))
X.sort(reverse=True)
MOD = int(1000000000.0 + 7)
pows_mod = [1]
for i in range(int(300000.0) + 10):
	pows_mod.append(pows_mod[-1] % MOD * 2 % MOD)
ans = 0
for i in range(N):
	ans += (pows_mod[N - i - 1] - 1 - (pows_mod[i] - 1)) * X[i]
	ans %= MOD
print(ans)


n = int(input())
x = sorted(map(int, input().split()))
mod = 10 ** 9 + 7
(ans, deg) = (0, 1)
dp = [0] * n
for i in range(1, n):
	deg = (deg << 1) % mod
	dp[i] = (2 * dp[i - 1] + (x[i] - x[i - 1]) * (deg - 1)) % mod
	ans = (ans + dp[i]) % mod
print(ans)


N = int(300000.0 + 3)
MOD = int(1000000000.0 + 7)
pow2 = [1] * N
for i in range(1, N):
	pow2[i] = pow2[i - 1] * 2 % MOD
n = int(input())
arr = list(map(int, input().split()))
arr.sort()

def add(x, y):
	return (x % MOD + MOD + (y % MOD + MOD) + MOD) % MOD

def substract(x, y):
	return (x % MOD + MOD - (y % MOD + MOD) + MOD) % MOD

def multiple(x, y):
	return x % MOD * (y % MOD) % MOD
res = 0
for i in range(1, n):
	diff = arr[i] - arr[i - 1]
	cnt = multiple(substract(pow2[i], 1), substract(pow2[n - i], 1))
	res = add(res, multiple(cnt, diff))
print(res)


MOD = 10 ** 9 + 7
n = int(input())
xs = sorted(map(int, input().split()))
pows = [1]
for i in range(n):
	pows.append(2 * pows[-1] % MOD)
ans = 0
for (ind, (lx, rx)) in enumerate(zip(xs, xs[1:])):
	cntl = ind + 1
	cntr = n - cntl
	ans = (ans + (rx - lx) * (pows[cntl] - 1) * (pows[cntr] - 1)) % MOD
print(ans)


from __future__ import print_function
import sys
try:
	input = raw_input
except:
	pass

def read_int_line():
	return [int(x) for x in input().split(' ')]

def read_int():
	return int(input())

class TreeNode(object):

	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None

	def __str__(self):
		q = deque()
		ans = []
		q.append(self)
		ans.append(self.val)
		while q:
			cur = q.popleft()
			ans.append(cur.left.val if cur.left else 'null')
			ans.append(cur.right.val if cur.right else 'null')
			if cur.left:
				q.append(cur.left)
			if cur.right:
				q.append(cur.right)
		while ans and ans[-1] == 'null':
			ans.pop()
		return str(ans).replace("'null'", 'null')

def toTreeNode(s):
	l = eval(s.replace('null', 'None'))
	n = len(l)
	if not n:
		return None
	root = TreeNode(l[0])
	q = deque()
	q.append(root)
	i = 1
	while q and i < n:
		cur = q.popleft()
		if l[i] != None:
			cur.left = TreeNode(l[i])
			q.append(cur.left)
		i += 1
		if i >= n:
			break
		if l[i] != None:
			cur.right = TreeNode(l[i])
			q.append(cur.right)
		i += 1
	return root

class Djs:

	def __init__(self, n):
		self.w = [1] * n
		self.p = [-1] * n

	def find(self, x):
		p = self.p[x]
		if p == -1:
			return x
		else:
			self.p[x] = self.find(p)
			return self.p[x]

	def union(self, x, y):
		(x, y) = (self.find(x), self.find(y))
		if x == y:
			return
		if self.w[x] > self.w[y]:
			(x, y) = (y, x)
		self.p[x] = y
		self.w[y] += self.w[x]

	def roots(self):
		return [x for (x, y) in enumerate(self.p) if y == -1]

def doit():
	n = read_int()
	arr = read_int_line()
	ans = 0
	arr.sort()
	P = 10 ** 9 + 7
	base = 1
	for v in arr:
		ans += v * base
		ans %= P
		base *= 2
		base %= P
	base = 1
	for v in arr[::-1]:
		ans -= v * base
		ans %= P
		base *= 2
		base %= P
	print('%d' % ans)
try:
	while True:
		doit()
except EOFError:
	pass


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


import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
n = int(input())
a = list(map(int, input().split()))
m = 1000000007
s = 0
a.sort()
for i in range(n):
	s = (s + a[i] * (pow(2, i, m) - pow(2, n - 1 - i, m))) % m
print(s)


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
pw = [1 for i in range(n)]
for i in range(1, n):
	pw[i] = pw[i - 1] * 2 % mod
ans = 0
a.sort()
for i in range(1, n):
	ans += (pw[i] - 1) * (pw[n - i] - 1) % mod * (a[i] - a[i - 1]) % mod
	ans %= mod
print(ans)


from sys import stdin, stderr
from random import shuffle

def readInts():
	return map(int, stdin.readline().strip().split())

def print_err(*args, **kwargs):
	print(*args, file=stderr, **kwargs)

def solve(vs):
	modval = 10 ** 9 + 7
	return all_f(vs)

def expnm(a, b, m):
	if b == 0:
		return 1
	if b % 2 == 0:
		return expnm(a * a % m, b // 2, m)
	return a * expnm(a, b - 1, m) % m

def expnm2(a, b, m):
	out = 1
	mult = a
	while b > 0:
		if b % 2 == 0:
			mult *= mult
			b //= 2
		else:
			out *= mult
			b -= 1
		out %= m
	return out

def all_f_naive(ns):
	n = len(ns)
	ns.sort()
	out = 0
	m = 10 ** 9 + 7
	for x1ix in range(n - 1):
		for x2ix in range(x1ix + 1, n):
			c = x2ix - x1ix - 1
			d = ns[x2ix] - ns[x1ix]
			out += d * expnm(2, c, m)
			out %= m
	return out

def twos(n, m):
	v = 1
	out = []
	for _ in range(n + 1):
		out.append(v)
		v <<= 1
		v %= m
	return out

def all_f(ns):
	n = len(ns)
	ns.sort()
	out = 0
	m = 10 ** 9 + 7
	t = twos(n, m)
	for x1ix in range(n):
		v = ns[x1ix] * t[x1ix]
		v %= m
		out += v
		out %= m
		v = ns[x1ix] * t[n - x1ix - 1]
		v %= m
		out -= v
		out %= m
	return out

def all_f3(ns):
	n = len(ns)
	ns.sort()
	out = 0
	m = 10 ** 9 + 7
	for x1ix in range(n):
		v = ns[x1ix] * expnm(2, x1ix, m)
		v %= m
		out += v
		out %= m
		v = ns[x1ix] * expnm(2, n - x1ix - 1, m)
		v %= m
		out -= v
		out %= m
	return out

def all_f2(ns):
	n = len(ns)
	ns.sort()
	out = 0
	m = 10 ** 9 + 7
	for x1ix in range(n):
		v = ns[x1ix] * expnm2(2, x1ix, m)
		v %= m
		out += v
		out %= m
		v = ns[x1ix] * expnm2(2, n - x1ix - 1, m)
		v %= m
		out -= v
		out %= m
	return out

def run():
	(n,) = readInts()
	vs = list(readInts())
	print(solve(vs))
run()


def mp():
	return map(int, input().split())

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

def pt(x):
	print(x)

def ip():
	return input()

def it():
	return int(input())

def sl(x):
	return [t for t in x]

def spl(x):
	return x.split()

def aj(liste, item):
	liste.append(item)

def bin(x):
	return '{0:b}'.format(x)

def listring(l):
	return ' '.join([str(x) for x in l])

def ptlist(l):
	print(' '.join([str(x) for x in l]))
M = 1000000007
n = it()
x = lt()
expp = 1
x.sort()
m = 0
for i in range(n):
	m += (expp - 1) * x[i] % M
	m -= (expp - 1) * x[n - i - 1] % M
	m += M
	m %= M
	expp *= 2
	expp %= M
pt(m)


n = int(input())
l = sorted(list(map(int, input().split())))
l = l[::-1]
MOD = 10 ** 9 + 7
power = []
two = 1
for i in range(n + 3):
	power.append(two)
	two *= 2
	two %= MOD
ans = 0
for i in range(n):
	ans = (ans + l[i] * power[n - i - 1]) % MOD
	ans = (ans - l[i] * power[i]) % MOD
print(ans)