Problem:
 Score : 500 points    Problem Statement For two sequences S and T of length N consisting of 0 and 1 , let us define f(S, T) as follows:    Consider repeating the following operation on S so that S will be equal to T . f(S, T) is the minimum possible total cost of those operations.   Change S_i (from 0 to 1 or vice versa). The cost of this operation is D \times C_i , where D is the number of integers j such that S_j \neq T_j (1 \leq j \leq N) just before this change.     There are 2^N \times (2^N - 1) pairs (S, T) of different sequences of length N consisting of 0 and 1 . Compute the sum of f(S, T) over all of those pairs, modulo (10^9+7) .      Constraints  1 \leq N \leq 2 \times 10^5  1 \leq C_i \leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  C_1  C_2  \cdots  C_N       Output Print the sum of f(S, T) , modulo (10^9+7) .        Sample Input 1 1
1000000000      Sample Output 1 999999993  There are two pairs (S, T) of different sequences of length 2 consisting of 0 and 1 , as follows:   S = (0), T = (1): by changing S_1 to 1 , we can have S = T at the cost of 1000000000 , so f(S, T) = 1000000000 .  S = (1), T = (0): by changing S_1 to 0 , we can have S = T at the cost of 1000000000 , so f(S, T) = 1000000000 .   The sum of these is 2000000000 , and we should print it modulo (10^9+7) , that is, 999999993 .       Sample Input 2 2
5 8      Sample Output 2 124  There are 12 pairs (S, T) of different sequences of length 3 consisting of 0 and 1 , which include:   S = (0, 1), T = (1, 0)   In this case, if we first change S_1 to 1 then change S_2 to 0 , the total cost is 5 \times 2 + 8 = 18 . We cannot have S = T at a smaller cost, so f(S, T) = 18 .       Sample Input 3 5
52 67 72 25 79      Sample Output 3 269312

Solution (Python):
mod = 10**9+7
N = int(input())
C = list(map(int,input().split()))
C.sort(reverse=True)
ans = 0
for i in range(N):
    ans += (i+2)*C[i]
    ans %= mod
ans *= pow(2,2*N-2,mod)
print(ans%mod)

Solution (Python):

N = int(input())

C = list(map(int,input().split()))

C.sort()

ans = 0

mod = 10 ** 9 + 7
two = [1]

for i in range(N+10):
    two.append(two[-1] * 2 % mod)

for i in range(N):

    ans += C[i] * ((two[N-1] * two[N-1] * (N-1-i)) + two[N-1] * two[N] )
    ans %= mod

print (ans)

Solution (Python):
n=int(input())
c=list(map(int,input().split()))
c.sort(reverse=1)
m=10**9+7
d=(2**(n-2))%m
ans=0
k=2
for x in c:
  x=int(x%m)
  ans+=(x*k*d)%m
  k+=1
ans=(int(ans)%m*d*4)%m

print(int(ans))

Solution (Python):
def main():
    N = int( input())
    Q = 10**9+7
    C = list( map( int, input().split()))
    C.sort()
    ans = 1
    if N == 1:
        print(C[0]*2%Q)
        return
    for i in range(N-1):
        ans += pow(2,i,Q)*(((N-1)-i)*pow(2,N-2-i,Q) + pow(2, N-1-i, Q))*C[i]%Q
        ans %= Q
    ans += pow(2, N-1, Q)*C[N-1]%Q
    ans -= 1
    print(ans*pow(2,N,Q)%Q)
if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
C = list(map(int,input().split()))
M = 10**9+7
C.sort(reverse=True)
ans = 0
tmp = 0
for i in range(N):
    if i == 0:
        t = tmp + pow(2,2*N-1,M)
    else:
        t = tmp + pow(2,2*N-2,M)
    ans += t*C[i]
    tmp = t

print(ans%M)

Solution (Python):
n = int(input())
c = sorted(list(map(int, input().split())))[::-1]
M = int(1e9+7)
power = [1]
for i in range(200005):
    power.append(2*power[i] % M)
ans = 0
for i in range(n):
    ans += 2 * power[i] * (i * power[i-1] + power[i]) * c[i] * power[n-i-1]**2 % M
    ans %= M
print(ans)

Solution (Python):
MOD = 10**9 + 7
n = int(input())
c = list(map(int, input().split()))
c.sort()

if n > 1:
    ans = 0
    x = (1 << (n - 1)) % MOD
    y = (1 << (n - 2)) % MOD
    for i in range(n):
        m = x + (y * (n - 1 - i)) % MOD
        m %= MOD
        ans += c[i] * m
        ans %= MOD

    for i in range(n):
        ans *= 2
        ans %= MOD
else:
    ans = c[0] * 2
    ans %= MOD
print(ans)

Solution (Python):
MOD=10**9+7

N=int(input())
if N==1:
  C=int(input())
  print(2*C%MOD)
  exit()
C=list(map(int, input().split()))
C.sort(reverse=True)
out=0
tmp1=pow(2, N-1, MOD)
tmp2=pow(2, N-2, MOD)
for i in range(N):
  out+=(tmp1+tmp2*i)*C[i]
  out%=MOD
  
out=out*pow(2, N, MOD)
print(int(out%MOD))

Solution (Python):
N = int(input())
C = sorted(list(map(int, input().split())), reverse=True)

ans = 0
mod = 10**9+7
for r, c in enumerate(C):
    ans += c*(r+2)

ans = ans * 2**(2*N-2) % mod
print(ans)

Solution (Python):
N=int(input())
C=sorted(map(int,input().split()),reverse=1)
m=10**9+7
x=pow(2,N-1,m)
r=0
for i in range(N):
    r+=C[i]*x%m
    if N>1:
        x+=pow(2,N-2,m)
print(pow(2,N,m)*r%m)

Solution (Python):
n = int(input())
c = list(map(int, input().split()))

c.sort(reverse = True)
ans = 0
f = 1
g = 1
for i in range(n-1):
    f *= 2
    f %= 10**9+7

for i in range(n-2):
    g *= 2
    g %= 10**9+7



for i in range(n):
    ans += f*c[i]
    f += g
    f %= 10**9+7
    ans %= 10**9+7


for i in range(n):
    ans *= 2
    ans %= 10**9+7

print(ans)

Solution (Python):
N = int(input())
*C, = map(int,input().split())

mod = 10**9+7

C.sort()

ans = 0
for i,c in enumerate(C):
    tmp = (pow(2,N-1-i,mod) + pow(2,max(0,N-2-i),mod)*(N-1-i))%mod
    tmp = (tmp*c)%mod
    tmp = (tmp*pow(2,i,mod))%mod
    ans += tmp
    ans %= mod
ans *= pow(2,N,mod)
ans %= mod
print(ans)

Solution (Python):
MOD = 10 ** 9 + 7










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

Solution (Python):
MOD = 10**9+7
n = int(input())
S = [1]*n
D = [1]*(n+1)
for i in range(n):
  D[i+1] = D[i]*2 % MOD
for i in range(n-1):
  S[i+1] = (S[i]*2 + D[i+1]) % MOD
T = S[::-1]
C = sorted(list(map(int, input().split())))
ans = 0
for i in range(n):
  ans += C[i]*((D[n-(i+1)]+T[i])*D[i]) % MOD
  ans %= MOD
ans = ans*D[n-1]%MOD
print(ans)

Solution (Python):
mod = 10**9+7

n = int(input())
c = list(map(int, input().split()))
c.sort()
left = 1
ans = 0
for i in range(n):
    k = n-1-i
    if k:
        cnt = pow(2, k, mod) + k*pow(2, k-1, mod)
        cnt *= pow(2, k, mod)
    else:
        cnt = 1
    ans += left*2*c[i]*cnt
    ans %= mod
    left *= 4
    left %= mod
print(ans)

Solution (Python):
n=int(input())
MOD=10**9+7
c=list(map(int,input().split()))
c.sort(reverse=True)
x=1
for i in range(n-1):
    x=(x*2)%MOD
x=(x*x)%MOD

ans=0
for i in range(n):
    tmp=(c[i]*(i+2))%MOD
    ans+=(tmp*x)%MOD
    ans%=MOD
print(ans)

Solution (Python):

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())
C=list(map(int,input().split()))
C.sort(reverse=True)
if n==1:
    print((C[0]*2)%mod)
    exit()
k=pow(2,n,mod)
k_dash=pow(2,n-1,mod)
k_prime=pow(2,n-2,mod)
exp=k_dash
for i,ci in enumerate(C):
    count=(count+ci*exp)%mod
    
    exp=(exp+k_prime)%mod
print((count*k)%mod)

Solution (Python):

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
a = [int(item) for item in input().split()]

a.sort(reverse=True)
ans = 0
inv2 = pow(2, MOD-2, MOD)
for i, item in enumerate(a):
    k = i + 1
    total = pow(2, 2 * n - k, MOD)
    coef = (k + 1) * pow(2, k-1, MOD) * inv2
    val = total * coef * item % MOD
    ans += val
    ans %= MOD
    
print(ans)

Solution (Python):
n = int(input())
ccc = list(map(int, input().split()))
ccc.sort()
MOD = 10 ** 9 + 7
ans = 0
others = pow(4, n - 1, MOD)
for i, c in enumerate(ccc):
    ans = (ans + others * c * (n - i + 1)) % MOD
print(ans)

Solution (Python):
N = int(input())
c = list(map(int, input().split()))
c.sort(reverse = True)
mod = 10 ** 9 + 7
tmp = (2 ** (N - 1)) % mod
d  = (2 ** (N - 2)) % mod
ans = 0
for ci in c:
    ans += (ci * tmp) % mod
    ans %= mod
    tmp = (tmp + d) % mod
print((ans * 2 ** N) % mod)

Solution (Python):
n=int(input())
C=[int(i) for i in input().split()]
mod=10**9+7
C.sort()
P=[0]*(2*n+1)
P[0]=1
for i in range(1,2*n+1):
  P[i]=(P[i-1]*2)%mod

ans=0
for i in range(n):
  ans=(ans+(n-i+1)*P[2*n-2]*C[i])%mod
print(ans)

Solution (Python):
MOD = 10**9+7
n = int(input())
c = sorted(list(map(int, input().split())), reverse=True)
print((pow(4, n-1, MOD) * sum([(i+2) * x for i, x in enumerate(c)])) % MOD)

Solution (Python):
N = int(input())
C = list(map(int, input().split()))
MOD = 10 ** 9 + 7

C.sort(reverse=True)

pow2 = [1]
for _ in range(2 * N):
    pow2.append(pow2[-1] * 2 % MOD)

ans = 0
for i in range(N):
    ans += (i + 2) * C[i]
    ans %= MOD
ans *= pow2[2 * N - 2]
ans %= MOD

print(ans)

Solution (Python):
N = int(input())
C = list(map(int, input().split()))
MOD =  10 ** 9 + 7

P = [1] * (N + 1)
for i in range(1, N + 1):
  P[i] = P[i - 1] * 2 % MOD

C.sort(reverse = True)

ans = 0
k = P[N - 1] % MOD
for i in range(N):
  ans = (ans + k * C[i] * P[N]) % MOD
  k = (k + P[N - 2]) % MOD

print(ans)

Solution (Python):
n = int(input())
c = sorted([int(_) for _ in input().split()])
mod = 10**9 + 7
ans = 0
for i in range(n):
    ans += c[i] * pow(2, 2 * n - 2, mod) * (n - i + 1)
    ans %= mod
print(ans)

Solution (Python):
def main():
    n=int(input())
    a=list(map(int,input().split()))
    mod=10**9+7
    if n==1:
        print(2*a[0]%mod)
        return
    a.sort(key=lambda x:-x)
    mod=10**9+7
    ans=0
    for i in range(n):
        ans=(ans+pow(2,n-2,mod)*a[i]*(i+2))%mod
    ans=ans*pow(2,n,mod)%mod
    print(ans)

main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    mod = 10**9+7
    N = int(input())
    C = list(map(int, input().split()))

    C.sort()
    ans = 0
    for i, c in enumerate(C):
        
        a = N - i - 1
        if a != 0:
            ans = (ans + (c * pow(2, i, mod))%mod * (pow(2, a-1, mod) * (a+2))%mod) % mod
        else:
            ans = (ans + (c * pow(2, N-1, mod))%mod) % mod
    print((ans * pow(2, N, mod))%mod)


if __name__ == '__main__':
    main()

Solution (Python):
def examA():
    K, X = LI()
    if K*500>=X:
        ans = "Yes"
    else:
        ans = "No"
    print(ans)
    return

def examB():
    N = I()
    S = SI()
    ans = 0
    for i in range(N-2):
        if S[i:i+3]=="ABC":
            ans +=1
    print(ans)
    return

def examC():
    N = I()
    P = LI()
    Q = LI()
    Cp = [i for i in itertools.permutations(P,N)]; Cp.sort()
    Cq = [i for i in itertools.permutations(Q, N)]; Cq.sort()


    for k,i in enumerate(Cp):
        flag = True
        for j in range(N):
            if P[j]!=i[j]:
                flag = False
                break
        if flag:
            a = k
            break
    for k,i in enumerate(Cq):
        flag = True
        for j in range(N):
            if Q[j]!=i[j]:
                flag = False
                break
        if flag:
            b = k
            break
    ans = abs(a-b)
    print(ans)
    return

def gcd(x,y):
    if y==0:
        return x
    while(y!=0):
        x, y = y,x%y
    return x
def lcm(x, y):
    return x * y // gcd(x, y)
def examD():
    N, M = LI()
    A = LI()
    flag = 0
    for i in range(1,32):
        if A[0]%(2**i)==0:
            flag +=1
        else:
            break

    for a in A:
        cur = 0
        for i in range(1, 32):
            if a % (2 ** i) == 0:
                cur += 1
            else:
                break
        if cur!=flag:
            print(0)
            return
    cur = A[0]
    for i in range(1,N):
        cur = lcm(cur,A[i])
        if cur>2*M:
            print(0)
            return
    ans = 1 + (M-cur//2)//cur
    print(ans)
    return

def examE():
    N = I()
    C = LI(); C.sort(reverse = True)
    sumC = sum(C)
    sumC %=mod
    Cp = pow(2,N*2-2,mod)
    cur = (sumC*Cp*2) %mod

    for i in range(1,N):
        now = (Cp*C[i]*(i)) %mod
        cur +=now
        cur %=mod
    ans = cur
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

Solution (Python):
n=int(input())
c=list(map(int,input().split()))
c.sort(reverse=1)
ans=0
mod=10**9+7
m=pow(4,n-1,mod)
x=2*m%mod
for i in range(n):
  ans+=x*c[i]
  ans%=mod
  x+=m
  x%=mod
print(ans)

Solution (Python):
N = int(input())
C = list(map(int,input().split()))

C.sort(reverse=True)
ans = 0
mod = 10**9 + 7
if N>=2:
    t = 1
    for i in range(2*N-2):
        t*=2
        t%=mod
    for i in range(N):
        ans+=(i+2)*C[i]
        ans%=mod
    
    ans*=t
    ans%=mod
    print(ans)
else:
    print((2*C[0])%mod)

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy


from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return [list(map(int, input().split())) for _ in range(n)]

def extgcd(a,b): 
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return ( m + x%m ) % m
    
def nCk(n,k):
    res = 1
    a=n-k
    b=k
    for i in range(1,a+b+1):
        res = res*i%mod
    for i in range(1,a+1):
        res = res*mod_inv(i,mod)%mod
    for i in range(1,b+1):                                 
        res = res*mod_inv(i,mod)%mod
    return res
    
def main():
    n = inp()
    c = inpl()
    ans = 0
    c.sort()
    x = [pow(2,2*n-1,mod)]
    y = pow(2,2*n-2,mod)
    for _ in range(n-1):
        x.append((x[-1]+y)%mod)
    x.reverse()
    for i in range(n):
        ans += (x[i]*c[i])%mod
    ans %= mod
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10 ** 9 + 7

N = int(readline())
A = np.array(read().split(),np.int64)

A.sort()
x = (A * np.arange(N+1,1,-1) % MOD).sum() % MOD
x *= pow(2, N+N-2, MOD); x %= MOD
print(x)

Solution (Python):
n = int(input())
c = [int(i) for i in input().split()]
c.sort(reverse=True)
ans = 0
mod = 10 ** 9 + 7
no = n
for i, j in enumerate(c):
    if i == 0:
        ans += j * pow(2, no, mod)
    else:
        ans += j*(pow(2, i, mod)+pow(2, i-1, mod)*i) * \
            pow(2, no, mod)
    no -= 1
    ans %= mod
print(ans*pow(2,i,mod) % mod)

Solution (Python):
mod = 10**9+7
n = int(input())
c = [int(x) for x in input().split()]
c = sorted(c)

ans = 0

pow2 = [1]
for i in range(n+1):
    tmp = (pow2[-1]*2)%mod
    pow2.append(tmp)

for i in range(n):
    ans += pow2[n]*pow2[i]*((n-1-i)*pow2[n-2-i] + pow2[n-1-i])*c[i]
    ans %= mod

print(ans)

Solution (Python):
import sys,bisect
input = sys.stdin.readline

n = int(input())
c = list(map(int,input().split()))
c.sort()

mod = 10**9+7


se = pow(2,mod-2,mod)

res = 0
for i,e in enumerate(c):
    cnt = (pow(4,n,mod)%mod)*se%mod
    res = (res + (e*cnt))%mod
    res = (res + (e*pow(4,n-1,mod)%mod)*(n-1-i)%mod)%mod
print(res%mod)

Solution (Python):
n=int(input())
clist = list(map(int, input().split()))
clist=sorted(clist)
answer=0
kihon=(2**(n-1))%(10**9+7)
tas=(2**(n-2))%(10**9+7)
for i in range(n):
    answer+=clist[-i-1]*(kihon)
    answer=answer%(10**9+7)
    kihon+=tas

answer=(answer*(2**n))%(10**9+7)
print(answer)

Solution (Python):


N=int(input())
c=sorted([int(i) for i in input().split()])
mod=10**9+7
if N==1:
    print((2*c[0])%mod)
    exit()
ans=0
for k in range(N):
    a1=pow(2,N-2,mod)
    a2=(N-k+1)
    tmp=(a1*a2)%mod
    ans+=(c[k]*tmp)%mod
    ans%=mod
    
ans=ans*pow(2,N,mod)
ans%=mod
print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read



n,*c = [int(i) for i in read().split()]
c.sort(reverse=True)


MOD = 10**9+7

ans = 0
for i,ci in enumerate(c):
    ans += (i+2)*ci%MOD
    ans %= MOD

print(ans*pow(2,2*n-2,MOD)%MOD)

Solution (Python):
n = int(input())
c = list(map(int, input().split()))
MOD = 10**9 + 7

inv2 = pow(2, MOD - 2, MOD)
tmp = pow(2, n, MOD) * pow(2, n, MOD)

tmp %= MOD

c = sorted(c, reverse = True)
ans = 0
for i in range(n):
    ans += tmp * c[i] * (1 + inv2 * i)
    ans %= MOD
print((ans * inv2) % MOD)

Solution (Python):
N=int(input())
C=list(map(int,input().split()))
mod=10**9+7
C.sort(reverse=True)
C=[0]+C
ans=0
for k in range(1,N+1):
    num=(C[k]*pow(2,2*N-2,mod)%mod)*(k+1)%mod
    ans=(ans+num)%mod 
print(ans)

Solution (Python):

n = int(input())
c = list(map(int, input().split( )))

c.sort()



sm = 0
for i in range(n):
    sm += ((n-i)+1)*c[i]
    

mod = 10**9+7
sm *= pow(2,2*n-2,mod)
sm%=mod
print(sm)