Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1

if 0 in a:
  print(0)
  exit()
  
for num in a:
  ans *= num
  
if(ans > 10**18):
  print(-1)
  exit()
  
print(ans)

### FIXED CODE ###

n = int( input() )
A = list( map( int,input().split() ) )
 
if 0 in A:
  print( 0 )
else:
  ret = 1
  for a in A:
    ret = ret * a
    if ret > 10 ** 18:
      ret = -1
      break
  print( ret )
### BUGGY CODE ###

# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush
import math
def run():
    # import sys
    # A = list(map(int, sys.stdin.readline().split()))
    # all = sys.stdin.readlines()
    #N, *A = map(int, open(0))
    #N = int(input())
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))
    CD = [[0,0]]
    for _ in range(N):
        c,d = list(map(int, sysread().split()))
        CD.append([c,d])
    queue = []
    # (time, node, rest-coin)
    heappush(queue, (0, 1, S))

    min_times = [None for _ in range(N+1)]
    nodes = [0 for _ in range(N)]

    while nodes:
        time, node, coin = heappop(queue)
        if min_times[node] == None:
            min_times[node] = time
            del nodes[0]
        c, d = CD[node]
        for n_node, n_time, n_coin in to[node] + [(node, d, -c)]:
            if coin < n_coin:
                k = math.ceil((n_coin - coin) / c)
                n_time += k * d
                heappush(queue, (time + n_time, n_node, coin + c*k - n_coin))
            else:
                heappush(queue, (time + n_time, n_node, coin - n_coin))
    for s in min_times[2:]:
        print(s)
if __name__ == "__main__":
    run()

### FIXED CODE ###

import sys
readline = sys.stdin.readline
read = sys.stdin.read
 
n,m,s = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    u,v,a,b = [int(i) for i in readline().split()]
    u -= 1
    v -= 1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
 
 
cd = [int(i) for i in read().split()]
c = cd[::2]
d = cd[1::2]
 
 
from heapq import *
INF = 1<<61
M = 2500
if s >= M: s = M-1
dist = [[INF]*M for _ in range(n)] #startからの最短距離
dist[0][s] = 0
q = [(0,s,0)] #(そこまでの距離、銀の枚数、点)
 
while q:
    dv,num,v = heappop(q)
    if dist[v][num] < dv: continue
    if num+c[v] < M and dv+d[v] < dist[v][num+c[v]]:
        dist[v][num+c[v]] = dv + d[v]
        heappush(q, (dv + d[v], num+c[v] ,v))
    for to,a,b in g[v]:
        if num >= a and dv + b < dist[to][num-a]:
            dist[to][num-a] = dv + b
            heappush(q, (dv + b, num-a ,to))
    #print(q)
 
for i in range(1,n):
    print(min(dist[i]))
### BUGGY CODE ###

from itertools import product

H, W = map(int, input().split())
grid_A = [list(map(int, input().split())) for _ in range(H)]
grid_B = [list(map(int, input().split())) for _ in range(H)]
diff = []
M = 0
for A, B in zip(grid_A, grid_B):
    temp = [abs(a - b) for a, b in zip(A, B)]
    M = max(max(temp), M)
    diff.append(temp)
dp = [[[False]*((H+W)*(M+1)) for _ in range(W)] for _ in range(H)]
dp[0][0][diff[0][0]] = True
for i, j in product(range(H), range(W)):
    for m in range((H+W)*(M+1)):
        if dp[i][j][m]:
            if i + 1 < H:
                d = diff[i+1][j]
                dp[i+1][j][m + d] = True
                dp[i+1][j][abs(m - d)] = True
            if j + 1 < W:
                d = diff[i][j+1]
                dp[i][j+1][m + d] = True
                dp[i][j+1][abs(m - d)] = True
for i in range((H+W)*(M+1)):
    if dp[H-1][W-1][i]:
        print(i)
        break

### FIXED CODE ###

from itertools import product

def offset(a, b):
    result = 0
    if b == 0: return 0
    for i in range(b+1):
        if (a >> i) & 1:
            result |= (1 << b) >> i
    return result

H, W = map(int, input().split())
diff = [list(map(int, input().split())) for _ in range(H)]
M = 80
for i in range(H):
    B = list(map(int, input().split()))
    for j in range(W):
        diff[i][j] = abs(diff[i][j] - B[j])
dp = [[0]*W for _ in range(H)]
dp[0][0] = 1 << diff[0][0]
for i, j in product(range(H), range(W)):
    if (i, j) == (H-1, W-1): break
    if i+1 < H:
        k = diff[i+1][j]
        dp[i+1][j] |= (dp[i][j] >> k) | (dp[i][j] << k) | (offset(dp[i][j], k))
    if j+1 < W:
        k = diff[i][j+1]
        dp[i][j+1] |= (dp[i][j] >> k) | (dp[i][j] << k) | (offset(dp[i][j], k))
ans = dp[H-1][W-1]
print((ans & -ans).bit_length() - 1)
### BUGGY CODE ###

N, K = map(int, input().strip().split())
result = 0
num = N // K
result += num
if num == 2:
    result += num * (num - 1) * 3
elif num > 2:
    result += num * (num - 1) * 3
    result += num * (num - 1) * (num - 2)


if K % 2 == 1:
    print(result)
else:
    start = K // 2
    for a in range(start, N + 1, K):
        for b in range(a, N + 1, K):
            for c in range(b, N + 1, K):
                if a == b and b == c:
                    result += 1
                elif a == b or b == c:
                    result += 3
                else:
                    result += 6
    print(result)

### FIXED CODE ###

N, K = map(int, input().strip().split())
result = 0
num = N // K
result += num
if num == 2:
    result += num * (num - 1) * 3
elif num > 2:
    result += num * (num - 1) * 3
    result += num * (num - 1) * (num - 2)


if K % 2 == 1:
    print(result)
else:
    start = K // 2
    num = (N - start) // K + 1
    result += num
    if num == 2:
        result += num * (num - 1) * 3
    elif num > 2:
        result += num * (num - 1) * 3
        result += num * (num - 1) * (num - 2)
    print(result)
### BUGGY CODE ###

def main():
    import heapq
    class unionfind():
        #size:要素数,tree：unionfind木
        def __init__(self,size):#self,要素数
            self.size=size
            self.tree=[[i,1] for i in range(self.size)]#root,depth
        
        #rootを探す
        def root(self,index):
            if self.tree[index][0]==index:
                return index
            else:
                self.tree[index][0]=self.root(self.tree[index][0])
                return self.tree[index][0]
    
        #結合
        def unite(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1!=r2:
                d1,d2=self.tree[r1][1],self.tree[r2][1]
                if d1<=d2:
                    self.tree[r1][0]=r2
                    self.tree[r2][1]=max(d1+1,d2)
                else:
                    self.tree[r2][0]=r1
                    self.tree[r1][1]=max(d2+1,d1)
    
        #同じか判定
        def same(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            return r1==r2
    
        #連結成分の個数
        def component(self):
            return len({self.root(i) for i in range(self.size)})
    
    n=int(input())
    xy=[list(map(int,input().split())) for _ in [0]*n]
    xyz=[xy[i]+[i] for i in range(n)]
    x_sort=sorted(xyz,key=lambda x:x[0])
    y_sort=sorted(xyz,key=lambda x:x[1])
    g=[]
    for i in range(n-1):
        g.append([abs(x_sort[i+1][0]-x_sort[i][0]),x_sort[i][2],x_sort[i+1][2]])
        g.append([abs(y_sort[i+1][1]-y_sort[i][1]),y_sort[i][2],y_sort[i+1][2]])
    heapq.heapify(g)
    u=unionfind(n)
    cnt=0
    while g:
        d,i,j=heapq.heappop(g)
        if u.same(i,j)==False:
            cnt+=d
            u.unite(i,j)
    print(cnt)
main()

### FIXED CODE ###

def main():
    import heapq
    def root(index):
        if tree[index][0]==index:
            return index
        else:
            tree[index][0]=root(tree[index][0])
            return tree[index][0]

    def unite(index1,index2):
        r1=root(index1)
        r2=root(index2)
        if r1!=r2:
            d1,d2=tree[r1][1],tree[r2][1]
            if d1<=d2:
                tree[r1][0]=r2
                tree[r2][1]=max(d1+1,d2)
            else:
                tree[r2][0]=r1
                tree[r1][1]=max(d2+1,d1)

    def same(index1,index2):
        return root(index1)==root(index2)
    
    n=int(input())
    xy=[list(map(int,input().split())) for _ in [0]*n]
    xyz=[xy[i]+[i] for i in range(n)]
    x_sort=sorted(xyz,key=lambda x:x[0])
    y_sort=sorted(xyz,key=lambda x:x[1])
    
    tree=[[i,1] for i in range(n)]#root,depth
    g=[]
    heapq.heapify(g)
    for i in range(n-1):
        heapq.heappush(g,[abs(x_sort[i+1][0]-x_sort[i][0]),x_sort[i][2],x_sort[i+1][2]])
    for i in range(n-1):
        heapq.heappush(g,[abs(y_sort[i+1][1]-y_sort[i][1]),y_sort[i][2],y_sort[i+1][2]])

    cnt=0
    while g:
        d,i,j=heapq.heappop(g)
        if same(i,j)==False:
            cnt+=d
            unite(i,j)
    print(cnt)
main()
### BUGGY CODE ###

from collections import defaultdict

n = int(input())
s = input()
ans = 0
for i in range(1000):
    password = str(i).zfill(3)
    #print(password)
    for j in range(n):
        if s[j] == password[0]:
            for k in range(j + 1, n):
                if s[k] == password[1]:
                    for l in range(k + 1, n):
                        if s[l] == password[2]:
                            ans += 1
                            break
                    
                    break
            
            break
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

ans = 0
for i in range(1000):
    num = str(i).zfill(3)
    if S.find(num[0]) == -1:
        continue
    S1 = S[S.find(num[0]) + 1:]
    if S1.find(num[1]) == -1:
        continue
    S2 = S1[S1.find(num[1]) + 1:]
    if S2.find(num[2]) == -1:
        continue
    ans += 1

print(ans)
### BUGGY CODE ###

class SegmentTree:
    SENTINEL = (float('inf'), 0)

    def __init__(self, n):
        n2 = 1 << (n - 1).bit_length()
        self.n = n2
        self.data = [self.SENTINEL] * ((n2 << 1) - 1)
        self.offset = n2 - 1

    def create(self, aaa):
        s = self.offset
        t = s + len(aaa)
        self.data[s:t] = aaa
        for i in range(self.offset - 1, -1, -1):
            self.data[i] = min(self.data[i * 2 + 1], self.data[i * 2 + 2])

    def get_left_min(self, k):
        i = k + self.offset - 1
        ret = self.data[i]
        while i:
            if i % 2 == 0:
                ret = min(ret, self.data[i - 1])
            i = (i - 1) // 2
        return ret

    def get_right_min(self, k):
        i = k + self.offset + 1
        ret = self.data[i]
        while i:
            if i % 2 == 1:
                ret = min(ret, self.data[i + 1])
            i = (i - 1) // 2
        return ret


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

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

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


n, d = map(int, input().split())
aaa = list(map(int, input().split()))
seg_l = SegmentTree(n)
seg_r = SegmentTree(n)
costs_l = [((i - n + 1) * d + a, n - i - 1) for i, a in enumerate(reversed(aaa))]
costs_r = [(i * d + a, i) for i, a in enumerate(aaa)]
costs_l.reverse()
seg_l.create(costs_l)
seg_r.create(costs_r)

edges = set()
nd = (n - 1) * d
for i, a in enumerate(aaa):
    di = i * d

    if i > 0:
        base_cost, j = seg_l.get_left_min(i)
        edges.add((base_cost + di + a, j, i))
    if i < n - 1:
        base_cost, j = seg_r.get_right_min(i)
        edges.add((base_cost - di + a, i, j))

uft = UnionFind(n)
ans = 0
for c, i, j in sorted(edges):
    if uft.find(i, j):
        continue
    ans += c
    uft.union(i, j)

print(ans)


### FIXED CODE ###

from itertools import accumulate
from operator import itemgetter

n, d = map(int, input().split())
aaa = list(map(int, input().split()))
costs_l = [(-i * d + a, i) for i, a in enumerate(aaa)]
costs_r = [(i * d + a, i) for i, a in enumerate(aaa)]

costs_l = list(accumulate(costs_l, min))
costs_r = list(accumulate(reversed(costs_r), min))
costs_r.reverse()

hubs = set(map(itemgetter(1), costs_l))
hubs.intersection_update(map(itemgetter(1), costs_r))
hubs.add(0)
hubs.add(n - 1)
hubs = sorted(hubs)

ans = sum(aaa) - aaa[-1]
s = hubs[0]
for t in hubs[1:]:
    cls = costs_l[s][0]
    crt = costs_r[t][0]
    ans += crt - s * d
    ans += sum(min(cls + i * d, crt - i * d) for i in range(s + 1, t))
    s = t
print(ans)
### BUGGY CODE ###

#%%

#%%
n = int(input())

def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

l = factorize(n)


import itertools
c = list(itertools.product(range(2), repeat=len(l)))
#print(c)

flag = False
k = 10**15
for i in range((len(c)+1)//2):
    a = 1
    b = 1
    for j in range(len(c[i])):
        if c[i][j] == 0:
            a *= l[j]
        else:
            b *= l[j]
    k = min(k, a+b)
    

print(k-2)


### FIXED CODE ###

#%%
n = int(input())
a = 10**15


x = int(n**0.5)
x += 1
for i in range(x, 1, -1):
    if n%i == 0:
        a = i
        b = n//i
        break
#print(a, b)

if a == 10**15:
    print(n-1)
else:
    print(a+b-2)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    q = int(input())
    l = []
    b = 0
    count = 0
    for i in range(q):
        a = list(map(int,input().split()))
        if a[0] == 1:
            l.append(a[1])
            count += 1
            b += a[2]
        else:
            l.sort()
            x = l[(count-1)//2]
            
            ans = 0
            for i in l:
                ans += abs(x-i)
            print(x,ans+b)
if __name__ == "__main__":
    main()       

### FIXED CODE ###

import heapq

q = int(input())
l = []
r = []
ans = 0

for i in range(q):
    a = list(map(int,input().split()))
    if a[0] == 1:
        ans += a[2]
        if l == []:
            heapq.heappush(r,a[1])
            heapq.heappush(l,-a[1])
        else: 
            ll = -heapq.heappop(l)
            rr = heapq.heappop(r)
            if ll <= a[1] <= rr:
                heapq.heappush(r,rr)
                heapq.heappush(l,-ll) 
                heapq.heappush(r,a[1])
                heapq.heappush(l,-a[1]) 

            elif ll > a[1]:
                ans += ll-a[1]
                heapq.heappush(r,rr)
                heapq.heappush(r,ll) 
                heapq.heappush(l,-a[1])
                heapq.heappush(l,-a[1]) 
            else:
                ans += a[1] -rr
                heapq.heappush(l,-rr)
                heapq.heappush(l,-ll) 
                heapq.heappush(r,a[1])
                heapq.heappush(r,a[1]) 
        
    else:
        a = heapq.heappop(l)
        print(-a,ans)
        heapq.heappush(l,a)
### BUGGY CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
from functools import reduce

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

a.sort()

count = Counter(a)

b = [1 for i in range(max(a)+1)]

for aa in a:
    for j in range(2*aa,max(a)+1, aa):
        b[j] = 0

c = 0
for d in count.items():
    if d[1] == 1 and b[d[0]] == 1: c += 1

print(c)

### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
from functools import reduce

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

a.sort()

count = Counter(a)

b = [1]*(max(a) + 1)

for aa in a:
    for j in range(2*aa,len(b), aa):
        b[j] = 0

c = 0
for d in count.items():
    if d[1] == 1 and b[d[0]] == 1: c += 1

print(c)
### BUGGY CODE ###

n = int(input())
alist = list(map(int,input().split()))
b = []
for i in range(n):
    if i%2 == 0:
        front = int(i/2)
        b.insert(front,alist[-1-i])
    else:
        if i!=1:
            back = -int((i-1)/2)
            b.insert(back,alist[-1-i])
        else:
            b.append(alist[-1-i])
for j in range(n):
    print(b[j],end=" ")

### FIXED CODE ###

#C問題
N = int(input())
A = list(map(int,input().split()))
if N%2 == 0:
    front = []
    back = []
    for i in range(N):
        if i%2 == 1:
            front.append(A[i])
        else:
            back.append(A[i])
    front = front[::-1]
    for i in range(N//2):
        print(front[i],end=" ")
    for i in range(N//2):
        print(back[i],end=" ")
        
else:
    front = []
    back = []
    for i in range(N):
        if i%2 == 0:
            front.append(A[i])
        else:
            back.append(A[i])
    front = front[::-1]
    for i in range(N//2 + 1):
        print(front[i],end=" ")
    for i in range(N//2):
        print(back[i],end=" ")
### BUGGY CODE ###

A, B, K = list(map(int, input().split()))
l1 = {n for n in range(A, A + K)}
l2 = {n for n in range(B - K + 1, B + 1)}
l = sorted(list((l1 | l2) & {n for n in range(A, B+1)}))
for s in l:
    print(s)

### FIXED CODE ###

A, B, K = list(map(int, input().split()))
if K >= (B - A + 1) / 2 :
    for n in range(A, B+1):
        print(n)
else:
    for n in range(A, A + K):
        print(n)
    for n in range(B - K + 1, B + 1):
        print(n)
### BUGGY CODE ###

import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
answer=0
matched_flag=[False]*(N+1)
for answer in range(1,N**3): 
  matched_flag=[False]*(N+1)
  unchanged=True
  
  for i in range(1,N+1):
    if matched_flag[i] or len(amat[i]) == 0:
      continue
      
    ai_next = amat[i][-1]
    if i<ai_next and amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      unchanged=False
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    for i in range(1,N+1):
      if len(amat[i])>0:
        break
    else:
      print(answer)
      sys.exit()


### FIXED CODE ###

import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
answer=0
matched_flag=[False]*(N+1)
for answer in range(1,N**3):
  if N>900 and answer>3000:
    print(N*(N-1)//2)
    sys.exit()
  
  matched_flag=[False]*(N+1)
  unchanged=True
  
  for i in range(1,N+1):
    if matched_flag[i] or len(amat[i]) == 0:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      unchanged=False
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    for i in range(1,N+1):
      if len(amat[i])>0:
        break
    else:
      print(answer)
      sys.exit()
### BUGGY CODE ###

N,K = map(int, input().strip().split(' '))
S = input().strip()

# 奇数番目は1のカタマリの人数　偶数番目は0のカタマリの人数 両端は必ず1のカタマリの人数
now_state, now_count = '1', 0
L = []
Ladd = L.append
for i in range(len(S)):
  if S[i] == now_state:
    now_count += 1
  else:
    Ladd(now_count)
    # reset
    now_count = 1
    now_state = '1' if now_state == '0' else '0'
Ladd(now_count)
if now_state == '0':
  Ladd(0)

#print(L)
# 0の塊をj個ひっくり返す
# j==1のとき101の3個の和の最大
# j==2のとき10101の5個の和の最大
# j==jのとき101...1のj*2+1個の和の最大

def evenngram(n, _list):
  return [_list[i:i+n] for i in range(len(_list)-n+1) if i%2==0]

j = min(int((len(L)-1)/2), K) # 0のカタマリをひっくり返せるだけひっくり返す
tmp = evenngram(j*2+1, L)
tmp = max([sum(t) for t in tmp])
print(tmp)



### FIXED CODE ###

N,K = map(int, input().strip().split(' '))
S = input().strip()
l,r,now_max,now_zeros = 0,0,1,0
for r in range(1,N):
  if S[r-1] == '0':
    if S[r] == '0':
      continue
    else:
      now_zeros += 1
  else:
    if S[r] == '0':
      if now_zeros < K:
        continue
      else:
        now_max = max(r-l, now_max)
        now_zeros -= 1
        for _ in range(l,r):
          l += 1
          if S[l-1:l+1] == '01':
            break
    else:
      continue
now_max = max(r-l+1, now_max)
print(now_max)
### BUGGY CODE ###

from collections import Counter
import math
import sys
def solve():
    N = int(input())
    A = list(map(int,sys.stdin.readline().split()))

    counter = Counter(A)

    ans = 0
    for i in range(N):
        if counter[A[i]] >= 2:
            continue
        divisors = calc_divisors(A[i])
        for divisor in divisors:
            if divisor == A[i]:
                continue
            if counter[divisor] > 0:
                break
        else:
            ans += 1
    
    print(ans)

def calc_divisors(n):
    divisors = []
    for i in range(1,int(math.sqrt(n)+1)):
        if n % i == 0:
            divisors.append(i)
            if (i*i != n):
                divisors.append(n//i)

    return divisors

if __name__ == '__main__':
    solve()


### FIXED CODE ###

from collections import Counter
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    dp = [True] * (10 ** 6 + 1)
    counter = Counter(A)

    A.sort()
    ans = 0
    for a in A:
        if dp[a]:
            if counter[a] == 1:
                ans += 1
            i = a
            while i <= 10 ** 6:
                dp[i] = False
                i += a
    
    print(ans)

if __name__ == '__main__':
    solve()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

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

mod=10**9+7
D=[]
d0=pow(2,N-1,mod)

#D：係数の配列の作成
for i in range(N):
    if i==0:
        D.append(d0)
    else:
        D.append( (2*D[-1]-d0)*pow(2,mod-2,mod)+d0 )

#Ci*Diを最小にするため、最小のCiに最大のDiを掛けるため、降順ソートする
D.sort(reverse=True)

ans=0
for c,d in zip(C,D):
    ans+=c*d
    ans%=mod

ans=ans*pow(2,N,mod)

print ans%mod


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

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

mod=10**9+7
D=[]
d0=pow(2,N-1,mod)

#D：係数の配列の作成
for i in range(N):
    if i==0:
        D.append(d0)
    else:
        next=(2*D[-1]-d0)*pow(2,mod-2,mod)+d0
        D.append(next%mod)

#Ci*Diを最小にするため、最小のCiに最大のDiを掛けるため、Dは配列を逆順にしたものを足し合わせる
#modを取っているので、Dを降順ソートすると順番が崩れる
ans=0
for c,d in zip(C,D[::-1]):
    ans+=c*d
    ans%=mod

ans=ans*pow(2,N,mod)

print ans%mod
### BUGGY CODE ###

import numpy as np

s = input()
t = input()
len_s, len_t = len(s), len(t)
dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
for index_s in range(len_s):
  char_s = s[index_s]
  dp_s = dp[index_s]
  dp_ss = dp[index_s + 1]
  for index_t in range(len_t):
    if char_s == t[index_t]:
      dp_ss[index_t + 1] = dp_s[index_t] + 1
    else:
      dp_ss[index_t + 1] = max(dp_s[index_t + 1], dp_ss[index_t])
index_s, index_t = len_s - 1, len_t - 1
lcs_reverse = []
len_lcs = dp_ss[-1]
while len_lcs > 0:
  if s[index_s] == t[index_t]:
    lcs_reverse.append(s[index_s])
    index_s -= 1
    index_t -= 1
    len_lcs -= 1
  elif dp[index_s][index_t + 1] == len_lcs:
    index_s -= 1
  else:
    index_t -= 1
print(''.join(lcs_reverse[::-1]))

### FIXED CODE ###

s = input()
t = input()
len_s, len_t = len(s), len(t)
dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
for index_s in range(len_s):
  char_s = s[index_s]
  dp_s = dp[index_s]
  dp_ss = dp[index_s + 1]
  for index_t in range(len_t):
    if char_s == t[index_t]:
      dp_ss[index_t + 1] = dp_s[index_t] + 1
    else:
      dp_ss[index_t + 1] = max(dp_s[index_t + 1], dp_ss[index_t])
index_s, index_t = len_s - 1, len_t - 1
lcs_reverse = []
len_lcs = dp_ss[-1]
while len_lcs > 0:
  if s[index_s] == t[index_t]:
    lcs_reverse.append(s[index_s])
    index_s -= 1
    index_t -= 1
    len_lcs -= 1
  elif dp[index_s][index_t + 1] == len_lcs:
    index_s -= 1
  else:
    index_t -= 1
print(''.join(lcs_reverse[::-1]))