Problem: 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).

Submission attempts (in order):
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

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

#     S = np.array(S, dtype=bool)
#     T = np.array(T, dtype=bool)
#     C = np.array(C, dtype=int)
#     costs = np.msort(C[S != T])

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

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




import os
import sys

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(reverse=True)

assert pow(2, MOD - 2, MOD) == 500000004


def div2(a):
    return a % MOD * 500000004 % MOD


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


# (1+x)^k = kC0 * x^0 + kC1 * x^1 + kC2 * x^2 + ... + kCk * x^k
# (1+x)^k * x = kC0 * x^1 + kC1 * x^2 + kC2 * x^3 + ... + kCk * x^(k+1)

# kC0 * 1 + kC1 * 2 + kC2 * 3 + ... + kCk * (k+1)
def df(k):
    
    # https://mathtrain.jp/composite
    
    # f(x) = 1+x
    # g(x) = x^k
    # h(x) = x
    # g(f(x)) * h(x) = (1+x)^k * x
    # f'(x) = 1
    # g'(x) = kx^(k-1)
    # h'(x) = 1
    # g'(f(x)) = g'(f(x)) * f'(x) = k(1+x)^(k-1)
    # (g(f(x)) * h(x))' = g'(f(x)) * h(x) + g(f(x)) * h'(x)
    #                   = k(1+x)^(k-1) + (1+x)^k
    
    
    #                   = (k + 2) / 2 * 2^k
    return div2((k + 2) * pow2[k])


ans = 0
for k in range(N):
    
    ans += df(k) * C[k] * pow2[N - k - 1]
    ans %= MOD
print(ans * pow2[N] % MOD)


Verdicts: Runtime Error

Accepted