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.

Difficulty: competition

Starter code:

Solutions:
3
# Copyright (C) 2017 Sayutin Dmitry.
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License as
# published by the Free Software Foundation; version 3
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; If not, see <http://www.gnu.org/licenses/>.

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()


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)

import sys
import math

MOD = int(1e9 + 7)
line = lambda: list(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()
    return

main()


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(n):
        p2[i + 1] = (p2[i] * 2) % mod

    for i in range(n - 1):
        length = x[i + 1] - x[i]

        ans = (ans + length * (p2[i + 1] - 1) * (p2[n - 1 - i] - 1)) % mod

    print(ans)

def __starting_point():
    solve()
__starting_point()

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)
    


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()

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)

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))

#!/usr/bin/pypy3

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):
    #print(a,b)
    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()


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())
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)

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)

n=int(input())
V=list(map (int,input().split()))
V.sort()
Mod=int(1e9+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, 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)



# Made By Mostafa_Khaled


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, 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(3e5+3)
MOD = int(1e9+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)


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())
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())
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()
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)

n = int(input())
arr = list(map(int,input().split()))
arr.sort()
mod = 10**9 + 7

s = 0
ans = 0
m = 0
lAdd = 1
# print(arr)
for i in range(n-2,-1,-1):
    # print('---------')
    # print(arr[i])
    m+=lAdd
    m%=mod

    lAdd*=2
    lAdd%=mod

    s *= 2
    s %= mod
    s += arr[i+1]
    s %= mod

    # print(s,(((arr[i])*((1<<(n-i-1)) - 1))%mod))
    t = s-((m*arr[i])%mod)
    t+=mod
    t%=mod
    ans+=t
    ans%=mod
print(ans%mod)