Harryxun/stf_run huggingface dataset:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        if self.parents[x] > self.parents[y]:
            rx, ry = ry, rx
        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx

    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    def size(self, x):
        return -self.parents[self.root(x)]


n, m = map(int, input().split())
bridges = [tuple((int(i)-1 for i in input().split())) for _ in range(m)]
islands = UnionFind(n)
res = [n*(n-1)//2]
for a, b in bridges[:0:-1]:
    if islands.same(a, b):
        res.append(res[-1])
    else:
        res.append(res[-1] - islands.size(a) * islands.size(b))
        islands.unite(a, b)
print('\n'.join(map(str, res[::-1])))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**5)


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        if self.parents[x] > self.parents[y]:
            rx, ry = ry, rx
        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx

    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    def size(self, x):
        return -self.parents[self.root(x)]


n, m = map(int, input().split())
bridges = [tuple((int(i)-1 for i in input().split())) for _ in range(m)]
islands = UnionFind(n)
res = [n*(n-1)//2]
for a, b in bridges[:0:-1]:
    if islands.same(a, b):
        res.append(res[-1])
    else:
        res.append(res[-1] - islands.size(a) * islands.size(b))
        islands.unite(a, b)
print('\n'.join(map(str, res[::-1])))
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]


def main():
    while True:
        map = []
        count = 0
        try:
            for i in range(12):
                map.append([x for x in input()])

            for i in range(12):
                for j in range(12):
                    if map[i][j] == '1':
                        dfs(map, j, i)
                        count += 1
            print(count)
        except EOFError:
            break


def dfs(map, x, y):
    if x < 0 or y < 0 or x >= 12 or y >= 12:
        return

    map[y][x] = '0'
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        if next_x >= 0 and next_x < 12 and next_y >= 0 and next_y < 12:
            if map[next_y][next_x] == '1':
                dfs(map, next_x, next_y)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]


def main():
    while True:
        map = []
        count = 0
        for i in range(12):
            map.append([x for x in input()])

        for i in range(12):
            for j in range(12):
                if map[i][j] == '1':
                    dfs(map, j, i)
                    count += 1
        print(count)

        if not sys.stdin.readline():
            break


def dfs(map, x, y):
    if x < 0 or y < 0 or x >= 12 or y >= 12:
        return

    map[y][x] = '0'
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        if next_x >= 0 and next_x < 12 and next_y >= 0 and next_y < 12:
            if map[next_y][next_x] == '1':
                dfs(map, next_x, next_y)


if __name__ == '__main__':
    main()
n = int(input())
m = 10**12
a = (n**0.5)//1
for i in a:
  if n%i==0:
    m=min(m,i+(n/i)-2)
print(m)

### FIXED CODE ###

n = int(input())
 
b = 10**12
a = int((n**0.5)//1)
for i in range(1,a+1):
  if n%i==0:
    b = min(b,int(i+(n//i)-2))
print(b)
N,A,B= map(int,input().split(' '))
x=A*N
if x>B:
  print(str(B))
elif x=B:
  print(str(B))
else ;
  print(str(x))

### FIXED CODE ###

n,a,b=map(int,input().split())
print(min(n*a,b))
n = int(input())
t = [int(input()) for i in range(n)]


def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


print(lcm_list(t))

### FIXED CODE ###

#import math  
import fractions
from functools import reduce

N = int(input())
T = []
for i in range(N):
    T.append(int(input()))

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
ans = lcm_list(T)

print(ans)
n,m,x,y = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
aMAX = max(a)
bMIN = min(b)
if (a<b and a+1>x and a+1<=y):
  print("No War")
else:
  print("War")

### FIXED CODE ###

n,m,x,y = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a = max(a)
b = min(b)
if (a<b and a+1>x and a+1<=y):
  print("No War")
else:
  print("War")
A, B, K = map(int, input().split())
for i in range(K):
    if i%2 ==0 :
        if A%2 != 0;
            A-=1
        B+=A//2
        A=A//2
    else:
        if B%2 !=0 ;
            B-=1
        A+=B//2
        B=B//2
print(A, B)


### FIXED CODE ###

# coding: utf-8
A, B, K = map(int, input().split())
for i in range(K):
    if i%2 ==0 :
        if A%2 != 0:
            A-=1
        B+=A//2
        A=A//2
    else:
        if B%2 !=0:
            B-=1
        A+=B//2
        B=B//2
print(A, B)
A, B = [int(i) for i in input().split()]

if A+B > 9:
	print('error')
	return
print(A+B)

### FIXED CODE ###

def print_add():
	A, B = [int(i) for i in input().split()]

	if A+B > 9:
		print('error')
		return 
	print(A+B)
	return
	
print_add()
S = input()
l = len(S)

a = 0
count = 0

for i in range(l):
    a = int(S[l-i-1])
    for j in range(i+1,l):
        if int(S[l-j-1]) != 0:
            a += int(S[l-j-1])*10**(j-i)
            if j-i > 2:
                if a % 2019 == 0:
                    count += 1
            
print(count)

### FIXED CODE ###

N, K = map(int, input().split())

a = 0

for i in range(K,N+2):
  a += i*(2*N-i+1)//2 - i*(i-1)//2 + 1
  
a = a % (10**9+7)
print(int(a))
A, B, C, D = map(int,input().split())
if A+B > C+D:
  print("Left")
elif A+B = C+D:
  print("Balanced")
else:
  print("Right")

### FIXED CODE ###

A, B, C, D = map(int,input().split())
if A+B > C+D:
  print("Left")
elif A+B == C+D:
  print("Balanced")
else:
  print("Right")
n, m = map(int, input().split())
table = [[] for i in range(n+1)]
ans = [(1e9, 0) for i in range(n+1)]
def func(node, num, li):
    for i in li:
        if num < ans[i][0]:
            ans[i] = (num, node)
            func(i, num+1, table[i])
        # print(ans[2:])


# print(table)
for i in range(m):
    a, b = map(int, input().split())
    # print(table[min(a, b)])
    # table[min(a, b)].append(max(a, b))
    table[a].append(b)
    table[b].append(a)

# print(table)


num = 1



func(1, num, table[1])
# print(ans[2:])
ans_ = []
for i in ans[2:]:
    ans_.append(i[1])
# print(ans_)
if 1e9 in ans_:
    print("No")
else:
    print("Yes")
    for i in ans_:
        print(i)


# print(table)


### FIXED CODE ###

import queue

n, m = map(int, input().split())
table = [[] for i in range(n+1)]
ans = [(1e9, 0) for i in range(n+1)]
seen = [False for _ in range(n+1)]
seen[1] = True

for i in range(m):
    a, b = map(int, input().split())
    # print(table[min(a, b)])
    # table[min(a, b)].append(max(a, b))
    table[a].append(b)
    table[b].append(a)

q = queue.Queue()

q.put((1, table[1]))
while(not q.empty()):
    element = q.get()
    for i in element[1]:
        if seen[i]:
            continue
        ans[i] = element[0]
        seen[i] = True
        q.put((i, table[i]))


if 1e9 in ans[2:]:
    print("No")
else:
    print("Yes")
    for i in ans[2:]:
        print(i)
a = set(["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"])
s = input()
for i in range(len(s)):
    a.remove(s[i])
b = list(a).sort()
if b:
    print(s[i]+b[0])
else:
    for i in range(2,27):
        if s[-i] < s[-i+1]:
            break
        if i == 26:
            print(-1)
            exit()
    for j in sorted(s[-i+1:]):
        if j > s[-i]:break
    print(s[:-i]+j)


### FIXED CODE ###

a = set(["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"])
s = input()
if len(s)<26:
    b = list(a-set(s))
    b.sort()
    print(s+b[0])
else:
    for i in range(2,27):
        if s[-i] < s[-i+1]:
            break
        if i == 26:
            print(-1)
            exit()
    for j in sorted(s[-i+1:]):
        if j > s[-i]:break
    print(s[:-i]+j)
a, b = map(float, input().split())
print(((a*(100*b))//100)

### FIXED CODE ###

from fractions import Fraction
a, b = map(Fraction, input().split())

print(int(a*b))
def calc(value):
    res = 0
    while True:
        if len(value) == 1:
            break
        elif value[0] != value[-1] and value[0] != "x" and value[-1] != "x":
            res = -1
            break
        elif value[0] == value[-1]:
            value.pop(0)
            value.pop()
        else:
            value.extend("x") if value[0] == "x" else value.insert(0, "x")
            value.pop(0)
            value.pop()
            res += 1
    return res


def main():
    value = list(input())
    print(calc(value))


if __name__ == '__main__':
    main()


### FIXED CODE ###

s = input()
ns = s.replace('x', '')
if s == s[::-1]:
    print(0)
elif ns != ns[::-1]:
    print(-1)
else:
    cnt = 0
    i = 0
    j = len(s)-1
    while(i<j):
        if s[i]=='x' and s[j]!='x':
            cnt += 1
            j += 1
        elif s[i]!='x' and s[j]=='x':
            cnt += 1
            i -= 1
        i += 1
        j -= 1
    print(cnt)
import sys
sys.setrecursionlimit(10 ** 5)
n = int(input())
color = [-1] * n
neighbor = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = tuple(map(int, input().split()))
    neighbor[u - 1].append((v-1, w))
    neighbor[v - 1].append((u-1, w))
def col(u, c):
    color[u] = c
    for v, w in neighbor[u]:
        if color[v] < 0:
            col(v, (c + w) % 2)
col(0, 0)
for i in range(n):
    print(color[i])

### FIXED CODE ###

n, k = map(int, input().split())
s = input()
for i in range(n):
    if i == k - 1:
        print(s[i].lower(), end = '')
    else:
        print(s[i], end = '')
O = input()

E = input()

Ans = ""

for i in range(len(O)):
	Ans += O[i]
	Ans += E[i]
print(Ans)

### FIXED CODE ###

O = input()

E = input()

Ans = ""

for i in range(len(O)):
	Ans += O[i]
	if i < len(E):
		Ans += E[i]
print(Ans)
N, M = map(int, input().split())
heights = list(map(int, input().split()))
 
good = [True] * N
for m in range(0, M):
  A, B = [int(s)-1 for s in input.split()]
  if heights[A] >= heights[B]:
    good[B] = False
  elif heights[A] <= heights[B]:
    good[A] = False
    
count = 0
for obs in good:
  if obs: count += 1
    
print(count)

### FIXED CODE ###

N, M = map(int, input().split())
heights = list(map(int, input().split()))
 
greatest = [0] * N
for m in range(0, M):
  A, B = [int(s)-1 for s in input().split()]
  greatest[A] = max(greatest[A], heights[B])
  greatest[B] = max(greatest[B], heights[A])
    
count = 0
for i in range(0, N):
    count += heights[i] > greatest[i]
    
print(count)
n,k = map(int,input().split())
a = tuple(map(int,input().split()))
mod = 10**9+7
rng = 1001
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
dp = [[0 for i in range(n+1)] for j in range(k+1)]
dp[0][0] = 1
for i in range(1,k+1):
  x = a[i-1]
  for j in range(n+1):
    for t in range(min(n-j,x)+1):
      dp[i][j+t]=(dp[i][j+t]+dp[i-1][j]*cmb(n-j,t)*cmb(n-t,x-t))%mod
print(dp[k][n])

### FIXED CODE ###

n = int(input())
a = [list(input().split()) for i in range(n)]
b = input()
flg = 0
ans = 0
for i in range(n):
  if a[i][0] == b:
    flg = 1
  elif flg:
    ans += int(a[i][1])
print(ans)
input()
t = list(map(int,input().split()))
m = int(input())
for i in range(m):
    p,x = map(int,input().split())
    print(sum(t)-t[p-1]+x)

### FIXED CODE ###

a,x,b = input().split()
if x == '+':
    print(int(a)+int(b))
else:
    print(int(a)-int(b))
import numpy as np
h,w=map(int, input().split( ))
s=[input() for _ in range(h)]
a = [-1,0,1]
b=[-1,0,1]
n=[(i,j) for i in a for j in b]
#print(n)
ans=[["#"]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        tmp=0
        if s[i][j]=="#":
            continue
        for x,y in n:
            if 0<=i+x<h and 0<=j+y<w:
                if (x or y) and s[i+x][j+y]=="#":
                    tmp+=1
        ans[i][j]=str(tmp)
for i in range(h):
    print(''.join(ans[i]))

### FIXED CODE ###


h,w=map(int, input().split( ))
s=[input() for _ in range(h)]
a = [-1,0,1]
b=[-1,0,1]
n=[(i,j) for i in a for j in b]
#print(n)
ans=[["#"]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        tmp=0
        if s[i][j]=="#":
            continue
        for x,y in n:
            if 0<=i+x<h and 0<=j+y<w:
                if (x or y) and s[i+x][j+y]=="#":
                    tmp+=1
        ans[i][j]=str(tmp)
for i in range(h):
    print(''.join(ans[i]))
import itertools
from decimal import Decimal, ROUND_HALF_UP
for _ in range(int(input())):
    a, b = tuple(map(int, input().split())), tuple(map(int, input().split()))
    c = 0
    for i in itertools.permutations(b):
        s = 0
        for j in range(9):s += (a[j] + i[j]) * (a[j] > i[j])
        if s > 85:c += 1
    c /= 362880
    print("{} {}".format(Decimal(c).quantize(Decimal('0.00001'), rounding=ROUND_HALF_UP), Decimal(1 - c).quantize(Decimal('0.00001'), rounding=ROUND_HALF_UP)))


### FIXED CODE ###

import math
from decimal import Decimal, ROUND_HALF_UP
for _ in range(int(input())):
    a, b = tuple(sorted(map(int, input().split()), reverse = True)), tuple(sorted(map(int, input().split())))
    c = 0
    q = {():(0, 0)}
    for i in range(9):
        nq = {}
        for k in q:
            for j in b:
                if j not in k:
                    x = q[k][0] + (a[i] + j) * (a[i] > j)
                    y = q[k][1] + (a[i] + j) * (a[i] < j)
                    if x > 85:c += math.factorial(9 - i - 1)
                    elif y < 86:nq[tuple(list(k) + [j])] = (x, y)
        q = nq
    c /= 362880
    print("{} {}".format(Decimal(c).quantize(Decimal('0.000001'), rounding=ROUND_HALF_UP), Decimal(1 - c).quantize(Decimal('0.000001'), rounding=ROUND_HALF_UP)))
import numpy as np
import math
import collections
import bisect
 
 
def main():
    a, b, c, d = map(int, input().split())
 
    dp = [[[1 for k in range(2)] for i in range(d + 1)] for j in range(c + 1)]
    for k in range(2):
        for i in range(c + 1):
            for j in range(d + 1):
                dp[i][j][1] = 0
                if j < b or i < a:
                    dp[i][j][k] = 0
 
    for i in range(a, c + 1):
        for j in range(b, d + 1):
            # print(i, j, dp[i][j])
            if a == i and b == j:
                continue
            dp[i][j][0] = ((i * dp[i][j - 1][0]) % 998244353 + dp[i][j - 1][1]) % 998244353
            dp[i][j][1] = (j * (dp[i - 1][j][0] + dp[i - 1][j][1]) % 998244353) % 998244353
 
    print((dp[c][d][0] + dp[c][d][1]) % 998244353)
 
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

#import numpy as np
import math
import collections
import bisect


def main():
    a, b, c, d = map(int, input().split())

    dp0 = [[1 for i in range(d + 1)] for j in range(c + 1)]
    dp1 = [[0 for i in range(d + 1)] for j in range(c + 1)]
    for i in range(c + 1):
        for j in range(d + 1):
            if j < b or i < a:
                dp0[i][j] = 0
                dp1[i][j] = 0
    for i in range(a, c + 1):
        for j in range(b, d + 1):
            # print(i, j, dp[i][j])
            if a == i and b == j:
                continue
            dp0[i][j] = ((i * dp0[i][j - 1]) % 998244353 + dp1[i][j - 1]) % 998244353
            dp1[i][j] = (j * (dp0[i - 1][j] + dp1[i - 1][j]) % 998244353) % 998244353

    print((dp0[c][d] + dp1[c][d]) % 998244353)


if __name__ == '__main__':
    main()
import numpy as np

MOD = 10**9+7

D,T,E = input().split()
n= int(D)

arr = np.zeros((n+1,n+1),dtype=np.int16)
for i in range(3,n+1):
    arr[0,i] = 1

for i in range(1,n+1):
    sum_ = 0
    for j in range(3*i,n+1):
        sum_ += arr[i-1,j]
        sum_ %= MOD
        if j+3 >= n + 1:
            break
        arr[i,j+3] = sum_

ans = 0
for i in range(n+1):
    ans += arr[i,n]
    ans %= MOD
print(ans)










### FIXED CODE ###

D,T,S = [int(i) for i in input().split()]
out = 'Yes' if D <= T * S else 'No'
print(out)
H, W, A, B = map(int, input().split())
ans = [[0]*W for _ in range(H)]
X = [0]*W
fail = False
if H == 1 and B == 0:
  print("1"*A+"0"*(W-A))
elif W == 1 and A == 0:
  for _ in range(B):
    print(1)
  for _ in range(H-B):
    print(0)
else:
  for i in range(H):
    s = 0
    while X[s] >= B:
      s += 1
    c = 0
    while s < W and c < A:
      ans[i][s] = 1
      X[s] += 1
      s += 1
      c += 1
    if c < A:
      fail = True
      break
  print("\n".join(["".join([str(x) for x in a]) for a in ans]) if not fail else "No")

### FIXED CODE ###

H, W, A, B = map(int, input().split())
for _ in range(B):
  print("0"*A+"1"*(W-A))
for _ in range(H-B):
  print("1"*A+"0"*(W-A))
import math
a,b=map(int,input().split())
ans = int(a*b/math.gcd(a,b))
print(ans)

### FIXED CODE ###

import fractions
a,b=map(int,input().split())
ans = a*b//fractions.gcd(a,b)
print(ans)
h,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]

max_a=max(a for a,_ in ab)
dp = [0] * (h+max_a)

for i in range(0,h+max_a):
    if i==0:
        d[i]=0
    else:
        dp[i]=min(dp[i-a]+b for a,b in ab)
print(min(dp[h:])



### FIXED CODE ###

h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

max_a = max(a for a, _ in ab)
dp = [0] * (h+max_a)

for i in range(0, h+max_a):
    if i <= 0:
        dp[i] = 0
    else:
        dp[i] = min(dp[i-a] + b for a,b in ab) 

print(min(dp[h:]))
import sys

N = int(input())

co = []
x, y = map(int, input().split())
Amod = (x + y) % 2
flag = True
max_co = 0
for i in range(N - 1):
    x, y = map(int, input().split())
    co.append((x, y))

    if(Amod != (x + y) % 2):
        flag = False

    tmp = abs(x) + abs(y)
    if(tmp > max_co):
        max_co = tmp

if(flag is False):
    print(-1)
    sys.exit()

m = max_co
arm = "1" + " 1" * (m - 1)

ans_list = []
for x, y in co:
    ans = ""
    absxy = abs(x) + abs(y)
    ans += "UD" * ((max_co - absxy) // 2)

    if(x < 0):
        ans += "L" * abs(x)
    else:
        ans += "R" * x
    if(y < 0):
        ans += "D" * abs(y)
    else:
        ans += "U" * y
    ans_list.append(ans)

for a in ans_list:
    print(a)

### FIXED CODE ###

import sys

N = int(input())

co = []
x, y = map(int, input().split())
co.append((x, y))
Amod = (x + y) % 2
flag = True
max_co = abs(x) + abs(y)
for i in range(N - 1):
    x, y = map(int, input().split())
    co.append((x, y))

    if(Amod != (x + y) % 2):
        flag = False

    tmp = abs(x) + abs(y)
    max_co = max(max_co, tmp)

if(flag is False):
    print(-1)
    sys.exit()

ex2 = [1, 2, 4, 8, 16, 32]
expo = 32
# print(maxxy)
while(expo < max_co):
    expo *= 2
    ex2.append(expo)


ans_list = []
for x, y in co:
    if Amod == 0:
        x -= 1
        ans = "R"
    else:
        ans = ""

    for arm in reversed(ex2):
        # print("present", x, y)
        if abs(x) > abs(y):
            if x > 0:
                x -= arm
                ans = "R" + ans
            else:
                x += arm
                ans = "L" + ans
        else:
            if y > 0:
                y -= arm
                ans = "U" + ans
            else:
                y += arm
                ans = "D" + ans
    # print(x, y)

    ans_list.append(ans)

if Amod == 0:
    ex2.append(1)

print(len(ex2))
arm = ""
for a in ex2:
    arm += " " + str(a)
print(arm[1:])
for a in ans_list:
    print(a)
def compare(a, A):
    R=0
    for i in range(0, len(A)):
        if(a==A[i]):
            R+=1
        elif(a<A[i]):
            break
    return R

def result(R,a):
    if(R==a):
        return 0
    elif(a<R):
        return R-a
    return R

N = int(input())

a = list(map(int, input().split()))
a.sort()

R=0
T=compare(a[0],a)
R+=result(T,a[0])

for i in range(1, N):
    if(a[i] != a[i-1]):
        C=compare(a[i],a[T:])
        R+=result(C,a[i])
        T+=C

print(R)


### FIXED CODE ###

import math

a,b = map(int, input().split())

T = math.ceil((a+b)/2)

print(T)
S = int(input())
h = S / 3600
m = S % 3600 /60
s = S % 3600 % 60
print(h,m,s,sep=':')

### FIXED CODE ###

S = int(input())
h = S // 3600
m = S % 3600 // 60
s = S % 3600 % 60
print(h,m,s,sep=':')
n,k,s=map(int,input().split())
if s!=10**9:
  ans=[s]*k+[10**9]*(n-k)
else:
  ans=[s]*k+(10**9-1)*(n-k)
print(*ans)

### FIXED CODE ###

n,k,s=map(int,input().split())
if s!=10**9:
  ans=[s]*k+[10**9]*(n-k)
else:
  ans=[s]*k+[10**9-1]*(n-k)
print(*ans)
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, mod) * (n-i-1) + pow(2, n-i-1, mod) ) % mod * pow(2, n, mod) % mod
    ans %= mod

print(ans)

### FIXED 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)
import fractions as math
from functools import reduce
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
N=int(input())
A=list(map(int,input().split()))
tmp=lcm_list(A)
ans=0
for i in A:
  ans+=tmp/i
  ans%=(10**9+7)
print(int(ans))

### FIXED CODE ###

import fractions 
N=int(input())
A=list(map(int,input().split()))
t=A[0]
for i in range(1,N):
  t=(t*A[i])//fractions.gcd(t,A[i])
ans=0
for i in range(N):
  ans+=t//A[i]
print(ans%(10**9+7))