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



Sample input:
1
1000000000


Sample output:
999999993

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

# from libs.debug import debug

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N = int(sys.stdin.buffer.readline())
C = list(map(int, sys.stdin.buffer.readline().split()))

# @debug
# def f(S, T, C):
#     S = np.array(S, dtype=bool)
#     T = np.array(T, dtype=bool)
#     C = np.array(C, dtype=int)
#     costs = np.msort(C[S != T])
#     return int(np.dot(costs[::-1], np.arange(1, len(costs) + 1)))
#
#
# def test(N, C):
#     ans = 0
#     for s in itertools.product([True, False], repeat=N):
#         for t in itertools.product([True, False], repeat=N):
#             ans += f(s, t, C)
#             ans %= MOD
#     print(ans)
#
#
# test(N, C)

# R[d][i]: C が降順にソートされてるとして、C[i] が上から d 番目の大きさになる選び方の数
# R = np.zeros((N + 1, N), dtype=int)
# R[0] = 0
# R[1] = 1
# for r in range(2, N + 1):
#     for c in range(N):
#         R[r, c] = R[r - 1][:c].sum()
# # 自分より大きいのの選び方の総数
# print(R)
# # 順位かける
# print(R * np.arange(N + 1)[:, None])
# # 自分より小さいのの選び方をかける
# print(R * np.arange(N + 1)[:, None] * (2 ** np.arange(N)[::-1]))
# # 順位が小さいのに大きいのをかける
# print(R * np.arange(N + 1)[:, None] * (2 ** np.arange(N)[::-1]) * np.msort(C)[::-1])
# print((R * np.arange(N + 1)[:, None] * (2 ** np.arange(N)[::-1]) * np.msort(C)[::-1]).sum())
# # 同じ選び方が 2**N 個ある
# print((R * np.arange(N + 1)[:, None] * (2 ** np.arange(N)[::-1]) * np.msort(C)[::-1]).sum() * (2 ** N) % MOD)

# print()
# print(R * np.arange(N + 1)[:, None] * (2 ** np.arange(N)[::-1]))
# print((R * np.arange(N + 1)[:, None] * (2 ** np.arange(N)[::-1])).sum(axis=0))
# print(np.diff((R * np.arange(N + 1)[:, None] * (2 ** np.arange(N)[::-1])).sum(axis=0)))


if N == 1:
    arr = np.ones(1, dtype=int)
else:
    arr = np.arange(N, dtype=int) * pow(2, N - 2, MOD) + pow(2, N - 1, MOD)
ans = arr % MOD * np.msort(C)[::-1] % MOD
print(sum(ans) % MOD * pow(2, N, MOD) % MOD)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

# from libs.debug import debug

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N = int(sys.stdin.buffer.readline())
C = list(map(int, sys.stdin.buffer.readline().split()))
C.sort()

#
# @debug
# def f(S, T, C):
#     S = np.array(S, dtype=bool)
#     T = np.array(T, dtype=bool)
#     C = np.array(C, dtype=int)
#     costs = np.msort(C[S != T])
#     return int(np.dot(costs[::-1], np.arange(1, len(costs) + 1)))
#
#
# def test(N, C):
#     ans = 0
#     for s in itertools.product([True, False], repeat=N):
#         for t in itertools.product([True, False], repeat=N):
#             ans += f(s, t, C)
#             ans %= MOD
#     print(ans)
#
#
# test(N, C)

# R = np.zeros((N + 1, N), dtype=int)
# R[0] = 0
# R[1] = 1
# for r in range(2, N + 1):
#     for c in range(N):
#         R[r, c] = R[r - 1][:c].sum()
# print(R)
# print(R * np.arange(N + 1)[:, None])
# print(R * np.arange(N + 1)[:, None] * (2 ** np.arange(N)[::-1]))
# print(R * np.arange(N + 1)[:, None] * (2 ** np.arange(N)[::-1]) * np.msort(C)[::-1])
# print((R * np.arange(N + 1)[:, None] * (2 ** np.arange(N)[::-1]) * np.msort(C)[::-1]).sum())
# print((R * np.arange(N + 1)[:, None] * (2 ** np.arange(N)[::-1]) * np.msort(C)[::-1]).sum() * (2 ** N) % MOD)
#
# print()
# print(R * np.arange(N + 1)[:, None] * (2 ** np.arange(N)[::-1]))
# print((R * np.arange(N + 1)[:, None] * (2 ** np.arange(N)[::-1])).sum(axis=0))
# print(np.diff((R * np.arange(N + 1)[:, None] * (2 ** np.arange(N)[::-1])).sum(axis=0)))

if N == 1:
    arr = np.ones(1, dtype=int)
else:
    arr = np.full(N + 1, pow(2, N - 2, MOD), dtype=int)
    arr = arr.cumsum()[1:]
    arr %= MOD
# print(arr)
ans = arr * np.msort(C)[::-1] % MOD
print(sum(ans) % MOD * pow(2, N, MOD) % MOD)
# print(ans.sum() * pow(2, N, MOD) % MOD)

Submission status: Accepted

Solution code:
N = int(input())
C = list(map(int, input().split()))
C.sort(reverse=True)
MOD = 10**9+7
print(pow(4, N-1, MOD)*sum(i * c for i, c in enumerate(C, 2))%MOD)

Submission status: Accepted

Solution code:
"""
・あるTについて、とりうる全てのSで支払う最小コストの和は、どのようにTをとっても同じ
　→Tを00~0と考えて、最後に2**N倍（Tのとりうる個数倍）してあげるとよい
・そうすると、各桁を独立して調べていける。
　Cは明らかにソートしてよい。Dが大きいときはCの小さいものをあてがう。
　これにより、ある桁の左にある個数と右にある個数に着目して、それらがとりうる組み合わせの数は何通りあるか考えることで桁ごとの最小コストが分かり、
　それを全てのけたについて足し合わせたものに、2**Nかけるとこたえになる


"""

import sys
sys.setrecursionlimit(10**6)


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


ans = 0
# どうも公式ドキュメントによると、組み込み関数のpowの第三引数に値渡すとMODとってくれるらしいので、完全に無駄
# 速くないのでシフト演算とかで置き換えたほうがいいっぽい（どのみち使う必要ないのでやらないけど）
def pow_mod(x, n, mod):
    if n == 0:
        return 1 % mod
    elif n % 2 == 0:
        y = pow_mod(x, n//2, mod)
        return y * y % MOD
    else:
        return x * pow_mod(x, n-1, mod) % mod

for i in range(N):
    # 詳細は開設動画の通りだが、i桁目の右にr個の数字、左にlこの数字がある
    l = i
    r = N - i - 1
    # i桁目の寄与が C[i] * 2**l * (2**r + r * 2**(r-1))で、最後に2**Nをかける（Tのとり方が2**Nこあるので）
    # -> C[i] * 2**l * (2**(N+r) + r * 2**(r+N-1))
    ans += ((C[i] * pow(2, l, MOD)) % MOD * (pow(2, N+r, MOD) + r * pow(2, N+r-1, MOD))) % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
"""



"""

import sys
sys.setrecursionlimit(10**6)


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


ans = 0
# どうも公式ドキュメントによると、組み込み関数のpowの第三引数に値渡すとMODとってくれるらしいので、完全に無駄
def pow_mod(x, n, mod):
    if n == 0:
        return 1 % mod
    elif n % 2 == 0:
        y = pow_mod(x, n//2, mod)
        return y * y % MOD
    else:
        return x * pow_mod(x, n-1, mod) % mod

for i in range(N):
    # 詳細は開設動画の通りだが、i桁目の右にr個の数字、左にlこの数字がある
    l = i
    r = N - i - 1
    # i桁目の寄与が C[i] * 2**l * (2**r + r * 2**(r-1))で、最後に2**Nをかける（Tのとり方が2**Nこあるので）
    # -> C[i] * 2**l * (2**(N+r) + r * 2**(r+N-1))
    ans += ((C[i] * pow(2, l, MOD)) % MOD * (pow(2, N+r, MOD) + r * pow(2, N+r-1, MOD))) % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
cnt = 0
a, b = pow(2, n-1, MOD), 0 if n <= 1 else pow(2, n-2, MOD)
for i, x in enumerate(c):
    cnt += (a + b*i) * x
    cnt %= MOD

print(cnt * pow(2, n, MOD) % MOD)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read


def mod_pow(a, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 1:
        return a * mod_pow(a, p - 1, mod)
    else:
        return (mod_pow(a, p // 2, mod) % mod) ** 2 % mod


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

C.sort(reverse=True)
n = mod_pow(4, N - 1, mod)

answer = 0

for i, c in enumerate(C, 2):
    answer += i * c
    if answer > mod:
        answer %= mod

answer *= n
answer %= mod

print(answer)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read


def mod_pow(a, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 1:
        return a * mod_pow(a, p - 1, mod)
    else:
        return (mod_pow(a, p // 2, mod) % mod) ** 2 % mod


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

C.sort(reverse=True)
n = mod_pow(4, N - 1, mod)

answer = 0

for i, c in enumerate(C, 2):
    answer += i * c

answer *= n
answer %= mod

print(answer)

Submission status: Accepted

Solution code:
N = int(input())
C = list(map(int, input().split()))
C.sort(reverse = True)
#print(C)
sosu = 10 ** 9 + 7
K = dict()
K[-1] = 1
K[0] = 1
for i in range(1, N+1):
    a = K[i-1] * 2 % sosu
    K[i] = a
ans = 0
for i in range(N):
    #for j in range(1,circle):##j番目に大きい
    #    kkk = c(i, j-1) * 2 ** (N-i-1)###i+1番目に大きいものがj番目に大きくなるような選び方
    #    ans += C[i] * kake * j * kkk
    ans += (C[i] * K[N] * (K[i] + i * K[i-1]) * K[N-i-1]) % sosu
    ans %= sosu
print(int(ans))

Submission status: Accepted

Solution code:
#T=(0,0,...,0)
#に変換するためのコストの2^N倍
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
    #print(k,tmp)
ans=ans*pow(2,N,mod)
ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read

mod = 10**9 + 7
n, *clst = map(int, read().split())
clst.sort()
res = sum((n + 2 - i) * item for i, item in enumerate(clst, 1))
print((4**(n - 1) * res) % mod)

Submission status: Accepted

Solution code:
n,*c=map(int,open(0).read().split())
mod=10**9+7
c.sort(reverse=True)
ans=0
for i,x in enumerate(c):
	ans+=x*(i+2)%mod
	ans%=mod
print(ans*pow(4,n-1)%mod)

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

def make_table(size=10**6, p=MOD):
    fac = [None] * (size + 1)
    fac[0] = 1
    for i in range(size):
        fac[i+1] = fac[i] * (i + 1) % p
    ifac = [None] * (size + 1)
    ifac[size] = pow(fac[size], p-2, p)
    for i in range(size, 0, -1):
        ifac[i-1] = ifac[i] * i % p
    return fac, ifac

fac, ifac = make_table(2*10**5)

def comb(n, r, mod=MOD):
    if r > n or r < 0:
        return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

n, *c = map(int, sys.stdin.read().split())

def main():
    c.sort(reverse=True)
    res = 0
    # for i in range(n):
    #     cnt = 0
    #     for d in range(1, n+1):
    #         for j in range(d):
    #             cnt += comb(i, j) * comb(n-i-1, d-j-1) * (d - j) % MOD
        
    #     res += c[i] * cnt
    #     res %= MOD
    for i in range(n):
        res += c[i] * (i + 2)
        res %= MOD
    return res * 4 ** (n - 1) % MOD

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

N = int(input())
Cs = list(map(int, input().split()))

As = [1]
accA = 1
m = 2
for i in range(1, N):
    A = (accA + m) % MOD
    As.append(A)
    accA = (accA + A) % MOD
    m = m * 2 % MOD

m = 1
for i in reversed(range(N)):
    As[i] = As[i] * m % MOD
    m = m * 2 % MOD

Cs.sort(reverse=True)

ans = 0
for C, A in zip(Cs, As):
    ans += C * A % MOD

print(ans * pow(2, N, MOD) % MOD)

Submission status: Accepted

Solution code:
# 解説放送を見た
# https://youtu.be/9MphwmIsO7Q?t=5738

def main():
    mod = 10 ** 9 + 7

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

    c.sort()

    pw = [1]
    t = 1
    for _ in range(n):
        t = t * 2 % mod
        pw.append(t)

    ret = 0
    for l, x in enumerate(c):
        r = n - 1 - l  # lxr
        ret = (ret + x * pw[l] * (pw[r] + pw[r - 1] * r)) % mod

    ret = ret * pw[n] % mod

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

#コストの小さいbitから変更した方が得
C.sort()

ans=0
for i,c in enumerate(C):
    l=i
    r=N-l-1
    tmp=fac[r]%MOD
    tmp+=r*fac[r-1]%MOD if r>0 else 0
    tmp*=c*fac[l]%MOD
    ans+=tmp%MOD
ans*=fac[N]
ans%=MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 10 ** 9 + 7
    n = II()
    cc = LI()
    cc.sort()
    exp2 = [1]
    for x in range(1, n + 1):
        exp2.append(exp2[-1] * 2 % md)
    #print(exp2)
    ans = 0
    for i, c in enumerate(cc):
        s = exp2[n - 1 - i]
        if n - i - 1 != 0: s += (n - 1 - i) * exp2[n - 2 - i]
        s *= exp2[i] * c
        ans = (ans + s) % md
    ans = ans * exp2[n] % md
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

mod = 10**9+7

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

C.sort(reverse=True)

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

t = C[0]*A[N-1] % mod
for k in range(1, N):
    t = (t + C[k]*(A[N-1]+k*A[N-2])%mod) % mod
print(t*A[N]%mod)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

MOD = 10**9+7
N = int(readline())
C = list(map(int, readline().split()))
C.sort()

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

Submission status: Accepted

Solution code:
M=1000000007
N=int(input())
C=sorted(map(int,input().split()),reverse=True)
def pow(x,p):
  if(p==0):
    return 1;
  if(p%2):
    a=pow(x,p-1)%M;
    return x*a%M
  else:
    a=pow(x,p//2)%M
    return a*a%M
ans=0;
p2=pow(2,2*N-2)%M
for k in range(N):
  ans=(ans+(C[k]*((p2*k)%M+2*p2))%M)%M
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
md = 10**9+7
N = int(input())
NN0 = (2**N)%md
NN1 = (2**(N-1))%md
NN2 = (2**(N-2))%md
C = list(map(int, input().split()))
C.sort()
ans = 0
for i in range(N):
    ans += ((C[i]%md) * NN1 )%md
    if i != (N-1):
        ans += ( (C[i]%md)*(N-1-i) * NN2 )%md
ans = (ans * NN0) %md
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
S,Tの両方動くが,片方固定して考える.(S = 0とする)
{
    (入力例2に対して)
    S = (0,0)と固定
    T = (0,0)の場合 S≠Tより考えない
    T = (0,1)の場合 8
    T = (1,0)の場合 5
    T = (1,1)の場合 min(5*2+8,8*2+5)
    よって, 8+5+min(5*2+8,8*2+5) = 31
    S = (0,1),(1,0),(1,1)に対しても同じ結果が得られる.
    つまり,S = (0,0)と固定したときの結果が分かれば2**nを掛けると答えが得られる
}
Cは降順ソートしておく.(並び順は関係ないので)
dp[i] := Σ(0<=j<=2**i) f(0,j)とするとans = dp[n]*(2**n)
dp[0] = C[0]
dp[i+1] := dp[i] + Σ(2**i<=j<=2**(i+1)-1) f(0,j) (右辺の左側はi+1桁目が0,右側はi+1桁目が1)
        := dp[i] + (2**i + i*(2**(i-1))*C[i] + dp[i] 
        := 2*dp[i] + (2**i + i*(2**(i-1)))*C[i]
        := 2*dp[i] + 2**(i-1)*(2+i)*C[i]
{
    (具体例(n=3))
    桁　3 2 1　個数
    --------------
        0 0 0
        0 0 1
        0 1 0
        0 1 1
        1 0 0　1(1*C[3]だけ増える)
        1 0 1　2(2*C[3]だけ増える)
        1 1 0　2(2*C[3]だけ増える)
        1 1 1　3(3*C[3]だけ増える)

    3桁目を見ているとする
    0のとき,dp[2]の分だけ増える
    1のとき,(個数の和)*C[3]+dp[2]だけ増える
        個数の和を求めたいときに,縦で数える
        ⇒3桁目は2**2,2桁目は2**1,3桁目は2**1
        ⇒2**2 + 2*2**1
        3桁目は常に1,2桁目以下は半分だけ1
        つまり,i桁目では2**(i-1) + (i-1)*2**(i-2)
    よって,
    dp[3] = dp[2] + (2**2 + 2*2**(2-1))*C[3] + dp[2]
}
dpは常にmodを取り,2**iも常に計算していては間に合わないので逐次*2をしていく(modをとりながら)
"""
n = I()
c = LI()
c.sort(reverse=True)
dp = [0]*n
dp[0] = c[0]
p = 1
for i in range(n-1):
    dp[i+1] = (2*dp[i] + p*(2+i+1)*c[i+1]) % mod
    p *= 2
    p %= mod
p *= 2
p %= mod
print(dp[-1]*p % mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
S,Tの両方動くが,片方固定して考える.(S = 0とする)
{
    (入力例2に対して)
    S = (0,0)と固定
    T = (0,0)の場合 S≠Tより考えない
    T = (0,1)の場合 8
    T = (1,0)の場合 5
    T = (1,1)の場合 min(5*2+8,8*2+5)
    よって, 8+5+min(5*2+8,8*2+5) = 31
    S = (0,1),(1,0),(1,1)に対しても同じ結果が得られる.
    つまり,S = (0,0)と固定したときの結果が分かれば2**nを掛けると答えが得られる
}
Cは降順ソートしておく.(並び順は関係ないので)
dp[i] := Σ(0<=j<=2**i) f(0,j)とするとans = dp[n]*(2**n)
dp[0] = C[0]
dp[i+1] := dp[i] + Σ(2**i<=j<=2**(i+1)-1) f(0,j) (右辺の左側はi+1桁目が0,右側はi桁目が1)
        := dp[i] + (2**i + i*(2**(i-1))*C[i] + dp[i] 
        := 2*dp[i] + (2**i + i*(2**(i-1)))*C[i]
        := 2*dp[i] + 2**(i-1)*(2+i)*C[i]
{
    (具体例(n=3))
    桁　3 2 1　個数
    --------------
        0 0 0
        0 0 1
        0 1 0
        0 1 1
        1 0 0　1(1*C[3]だけ増える)
        1 0 1　2(2*C[3]だけ増える)
        1 1 0　2(2*C[3]だけ増える)
        1 1 1　3(3*C[3]だけ増える)

    3桁目を見ているとする
    0のとき,dp[2]の分だけ増える
    1のとき,(個数の和)*C[3]+dp[2]だけ増える
        個数の和を求めたいときに,縦で数える
        ⇒3桁目は2**2,2桁目は2**1,3桁目は2**1
        ⇒2**2 + 2*2**1
        3桁目は常に1,2桁目以下は半分だけ1
        つまり,i桁目では2**(i-1) + (i-1)*2**(i-2)
    よって,
    dp[3] = dp[2] + (2**2 + 2*2**(2-1))*C[3] + dp[2]
}
dpは常にmodを取り,2**iも常に計算していては間に合わないので逐次*2をしていく(modをとりながら)
"""
n = I()
c = LI()
c.sort(reverse=True)
dp = [0]*n
dp[0] = c[0]
p = 1
for i in range(n-1):
    dp[i+1] = (2*dp[i] + p*(2+i+1)*c[i+1]) % mod
    p *= 2
    p %= mod
p *= 2
p %= mod
print(dp[-1]*p % mod)

Submission status: Accepted

Solution code:
N = int(input())
C = list(sorted(map(int, input().split())))
mod = int(1e9 + 7)

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

ans = 0
for i in range(N):
    l, r = i, N - i - 1
    res = f[r]
    if r > 0:
        res += f[r-1] * r
    res = res * f[l] % mod
    res = res * C[i] % mod
    res = res * f[N] % mod
    ans = (ans + res) % mod
print(ans)

Submission status: Accepted

Solution code:
div = (10**9) + 7

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

c = sorted(c, reverse=True)

ans = 0

exp4_div = [0]*n
exp4_div[0] = 1
for i in range(1,n):
    exp4_div[i] = (exp4_div[i-1]*4)%div

for i in range(n):
    ans = (ans*4 + c[i] * (i+2) * exp4_div[i] ) % div

print(ans)

Submission status: Accepted

Solution code:
def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


N = int(input())
C = list(map(int, input().split()))
C.sort(reverse=True)

MOD = 10**9 + 7
ans = 0

for i, c in enumerate(C, 1):
  ans += c*(i+1) % MOD

ans *= power(4, N-1)
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
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=sum([a[i]*(i+2)%mod for i in range(n)])
    ans=ans*pow(2,n,mod)*pow(2,n-2,mod)%mod
    print(ans)

main()

Submission status: Accepted

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

mod = 10**9 + 7
c.sort()
ans = 0
# python3.4.3では, powは、modを指定した場合、第二引数が負だとエラーを返す。3.8.0では問題なかった
for i in range(n):
    ans += c[i] * pow(2, i, mod) % mod * (pow(2, n-i-2+n, mod) * (n-i-1) + pow(2, n-i-1+n, mod)) % mod
    ans %= mod

print(ans)

Submission status: Accepted

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

mod = 10**9 + 7
c.sort()
ans = 0

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
c = LI()
c.sort(reverse=True)
dp = [0]*n
dp[0] = c[0]
p = 1
for i in range(n-1):
    dp[i+1] = (2*dp[i] + p*(2+i+1)*c[i+1]) % mod
    p *= 2
    p %= mod
p *= 2
p %= mod
print(dp[-1]*p % mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
S,T
"""

n = I()
c = LI()
c.sort(reverse=True)
dp = [0]*n
dp[0] = c[0]
p = 1
for i in range(n-1):
    dp[i+1] = (2*dp[i] + p*(2+i+1)*c[i+1]) % mod
    p *= 2
    p %= mod
p *= 2
p %= mod
print(dp[-1]*p % mod)

Submission status: Accepted

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

a = 10**9+7
C = list(reversed(sorted(C)))

count = 0
# Cに掛ける数
# N=1 1
# N=2 2, 3
# N=3 4, 6, 8
# N=4 8, 12, 16, 20
for i in range(0, N):
    count += C[i] * (2+i)

print(count * 4**(N-1) % a)

Submission status: Accepted

Solution code:
def e_change_a_little_bit(MOD=10**9 + 7):
    N = int(input())
    C = [int(i) for i in input().split()]

    C.sort(reverse=True)
    ans = 0
    for i in range(N):
        ans += C[i] * (i + 1 + 1)
    ans *= 4**(N - 1)
    return ans % MOD

print(e_change_a_little_bit())

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    c = LI()
    c.sort(reverse = True)
    dp = [0]*n
    dp[0] = c[0]
    p = 1
    for i in range(n-1):
        ni = i+1
        dp[ni] = (2*dp[i]+p*(2+ni)*c[ni])%mod
        p *= 2
        p %= mod
    p *= 2
    p %= mod
    print(p*dp[n-1]%mod)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

MOD = 1000000000 + 7
N = int(readline())
C = np.array(read().split(), np.int64)

C.sort()

ans = (C * np.arange(N+1, 1, -1) % MOD).sum() % MOD
ans *= pow(2, N+N-2, MOD)

print(ans % MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

def main():
	n=int(input())
	c=list(map(int,input().split()))
	c.sort()
	c=c[::-1]
	
	ans=0
	nn=[1]
	for i in range(n+1):
		nn.append(nn[-1]*2%mod)
		
	a=nn[n]
	
	for i in range(n):
		aa=c[i]%mod
		aaa=nn[n-1]+((i)*nn[n-2])%mod
		ans+=(a*aa*aaa)
		ans%=mod
		
	print(int(ans))
	
	
	


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    C = [int(c) for c in input().split()]
    C.sort()
    mod = 7 + 10 ** 9

    SumC = 0

    for i in range(N):
        SumC += (C[i] * (N - i + 1)) % mod
        SumC %= mod
    SumC *= pow(4, N - 1, mod)
    SumC %= mod
    print(SumC)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
mod=10**9+7
n, *clst = map(int, read().split())
if n == 1:
  print(clst[0]*2%mod)
  quit()
clst.sort(reverse=True)
res=sum(i*item for i, item in enumerate(clst,2))
print((4**(n-1)*res)%mod)

Submission status: Accepted

Solution code:
import sys

n = int(input())
c_ls = [int(i) for i in sys.stdin.readline().split()]
c_ls.sort(reverse=True)
MOD = 10 ** 9 + 7

res = 0
for i, c in enumerate(c_ls):
    res += (i + 2) * c % MOD
    res %= MOD
res = res * (4 ** (n - 1)) % MOD
print(int(res))

Submission status: Accepted

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

C.sort()

ans = 0

mod = 10 ** 9 + 7

pattern = (2 ** (N - 2)) % mod

if N != 1:
    for i in range(N):
        c = C[i]
        ans += c * (N + 1 - i) * pattern
        ans %= mod
    ans *= 2 ** N
else:
    ans = C[0] * 2

ans %= mod

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
c = sorted(list(map(int, input().split())))
mod = 10 ** 9 + 7
ans = 0
for i,v in enumerate(c):
  ans = (ans + (v * pow(2,n+i,mod) * ((n-i-1) * pow(2,max(0,n-i-2),mod) + pow(2,n-i-1,mod))) % mod) % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (10)
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )

N, = map(int, input().split())
xs = list(map(int, input().split()))
xs.sort()
r = 0
for i, x in enumerate(xs[::-1]):
    r = (r + mul(((i+1)+1),x))%mod
f = power(2,N)
r = mul(mul(mul(r, f),f), inverse[4])
print(r)

Submission status: Accepted

Solution code:
n = int(input())
C = list(map(int, input().split()))

mod = 10**9 + 7

if n == 1:
    ans = 2 * C[0]
    ans %= mod
    print(ans)
    exit()


ans = 0
pattern = 2 ** (n-1) % mod
d = 2 ** (n-2) % mod
C.sort(reverse=True)
for c in C:
    ans += (c * pattern) % mod
    pattern += d
    pattern %= mod
    ans %= mod

print(ans*(2**n) % mod)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9+7
N = int(input())
C = list(map(int,input().split()))
C.sort(reverse=True)
nu = pow(2,N-1,MOD)
owt = pow(2,MOD-2,MOD)
A = [nu]*N
hoge = (nu*owt)%MOD
for i in range(1,N):
    A[i] = (A[i-1]+hoge)%MOD
ans = 0
for i in range(N):
    ans += A[i]*C[i]
    ans %= MOD
print((ans*pow(2,N,MOD))%MOD)

Submission status: Accepted

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


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

print(ans % MOD)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))

A.sort(reverse=True)

ans = 0
mod = 10**9+7

for i in range(n):
    ans = (ans+(i+2)*A[i])%mod
    # print(i,ans)

for i in range(n*2-2):
    ans = (ans*2) % mod

print(ans)

Submission status: Accepted

Solution code:
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)