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

def readinput():
    n=int(input())
    l=list(map(int,input().split()))
    return n,l

def main(n,a):
    MOD=10**9+7
    hist=[0]*61
    bs=[]
    for i in range(n):
        # s=list(reversed(bin(a[i])[2:]))
        # for j in range(len(s)):
        #     if s[j]=='1':
        #         hist[j]+=1
        # bs.append(s)
        # s=bin(a[i])[2:]
        # for j in range(len(s)):
        #     if s[j]=='1':
        #         hist[len(s)-j-1]+=1
        b=1
        j=0
        while b<=a[i]:
            if a[i]&b==b:
                hist[j]+=1
            b*=2
            j+=1


    #print(bs)
    #print(hist)
    sum=0
    # for i in range(n-1):
    #     s=bs[i]
    #     b=1
    #     for j in range(len(s)):
    #         if s[j]=='0':
    #             sum=(sum+hist[j]*b)%MOD
    #         else:
    #             sum=(sum+( n-i-hist[j] )*b)%MOD
    #             hist[j]-=1
    #         b*=2
    #     for j in range(len(s),61):
    #         sum=(sum+hist[j]*b)%MOD
    #         b*=2
    b=1
    for j in range(61):
        sum=(sum+( hist[j]*(n-hist[j])*b )%MOD )%MOD
        b*=2

    return sum

if __name__=='__main__':
    n,l=readinput()
    ans=main(n,l)
    print(ans)


### FIXED CODE ###

def readinput():
    n=int(input())
    l=list(map(int,input().split()))
    return n,l

def main(n,a):
    MOD=10**9+7
    hist=[0]*61
    bs=[]
    for i in range(n):
        # s=list(reversed(bin(a[i])[2:]))
        # for j in range(len(s)):
        #     if s[j]=='1':
        #         hist[j]+=1
        # bs.append(s)
        s=bin(a[i])[2:]
        for j in range(len(s)):
            if s[j]=='1':
                hist[len(s)-j-1]+=1

    #print(bs)
    #print(hist)
    sum=0
    # for i in range(n-1):
    #     s=bs[i]
    #     b=1
    #     for j in range(len(s)):
    #         if s[j]=='0':
    #             sum=(sum+hist[j]*b)%MOD
    #         else:
    #             sum=(sum+( n-i-hist[j] )*b)%MOD
    #             hist[j]-=1
    #         b*=2
    #     for j in range(len(s),61):
    #         sum=(sum+hist[j]*b)%MOD
    #         b*=2
    b=1
    for j in range(61):
        sum=(sum+( hist[j]*(n-hist[j])*b )%MOD )%MOD
        b*=2

    return sum

if __name__=='__main__':
    n,l=readinput()
    ans=main(n,l)
    print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(i) for i in input().split()]
a.sort()
for i in range(m):
    b,c = map(int,input().split())
    if a[0] < c:
        for j in range(b):
            a[j] = max(a[j],c)
    a.sort()
print(sum(a))


### FIXED CODE ###

from operator import itemgetter

n,m = map(int,input().split())
a = [int(i) for i in input().split()]
w = []
x = 0
for i in range(m):
    b,c = map(int,input().split())
    w.append((b,c))
w = list(sorted(w,key=itemgetter(1)))
w.reverse()
for i in w:
    a += [i[1]] * i[0]
    x += b
    if x > n:
        break
a.sort()
a = a[len(a)-n:]
print(sum(a))
### BUGGY CODE ###

from itertools import combinations_with_replacement

N,M,Q=map(int,input().split())
a=[0]*Q
b=[0]*Q
c=[0]*Q
d=[0]*Q
for i in range(Q):
  a[i],b[i],c[i],d[i] =map(int,input().split())

ans_list=[]  
from copy import deepcopy
def dfs(x,M,N,ans):
  if len(ans)<=N:
    ans.append(x)
    for i in range(x,M+1):
      tmp=deepcopy(ans)
      dfs(i,M,N,tmp)
  else:    
    if ans not in ans_list:
      ans_list.append(ans)
      
q=dfs(1,M,N,[])

f=0
for A in ans_list:
  cnt=0
  for i in range(Q):
    if A[b[i]-1]-A[a[i]-1]==c[i]:
      cnt += d[i]
  f=max(f,cnt)
  
print(f)

### FIXED CODE ###

N,M,Q=map(int,input().split())
a=[0]*Q
b=[0]*Q
c=[0]*Q
d=[0]*Q
for i in range(Q):
  a[i],b[i],c[i],d[i] =map(int,input().split())

ans_list=[]  
from copy import deepcopy
def dfs(x,M,N,ans):
  if len(ans)<=N:
    ans.append(x)
    if len(ans)==N:
      ans_list.append(ans)
    else:
      for i in range(x,M+1):
        tmp=deepcopy(ans)
        dfs(i,M,N,tmp)   
      
q=dfs(1,M,N,[])

f=0
for A in ans_list:
  cnt=0
  for i in range(Q):
    if A[b[i]-1]-A[a[i]-1]==c[i]:
      cnt += d[i]
  f=max(f,cnt)
  
print(f)
### BUGGY CODE ###

import math

H,N=map(int,input().split())
A_list=[]
B_list=[]
for i in range(N):
    A,B=map(int,input().split())
    A_list.append(A)
    B_list.append(B)

amax=max(A_list)

inf=float('inf')
dp=[0]+[inf]*(H+amax)

for i in range(N):
    A=A_list[i]
    B=B_list[i]
    for j in range(A,1+H+amax):
        if dp[j-A]+B<dp[j]:
            dp[j]=dp[j-A]+B

print(min(dp[H:]))


### FIXED CODE ###

import math

def main():
    H,N=map(int,input().split())

    inf=float('inf')
    dp=[0]+[inf]*H

    for i in range(N):
        A,B=map(int,input().split())
        if A>=H:
            #dp[-1]=min(B,dp[-1])
            if B < dp[-1]:
                dp[-1]=B
        else:
            for j in range(A,H+1):
                #dp[j]=min(dp[j-A]+B,dp[j])
                if dp[j-A]+B<dp[j]:
                    dp[j]=dp[j-A]+B

                if j > H-A:
                    #dp[-1]=min(dp[-1],dp[j]+B)
                    if dp[j]+B < dp[-1]:
                        dp[-1]=dp[j]+B

    print(dp[-1])

main()
### BUGGY CODE ###

X, K, D = map(int, input().split())
X = abs(X)
for i in range(K):
    if X >= D:
        X = X-D
    elif X < D and (K-i)%2==1:
        X = X-D
        break
    else:
        break
print(abs(X))

### FIXED CODE ###

X, K, D = map(int, input().split())
X = abs(X)
dis = X
if X >=D:
    dis = X - D*(min(abs(X)//D,K))
    K = K - min(abs(X)//D,K)
    if K%2==0:
        print(dis)
    else:
        print(abs(dis-D))
else:
    if K%2==0:
        print(dis)
    else:
        print(abs(dis-D))
### BUGGY CODE ###

n = int(input())
ln =list(map(int, input().split()))
a = 1
for i in ln:
    a *= i
if a > 10**18:
    print('-1')
else:
    print(a)
    

### FIXED CODE ###

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

for i in sorted(ln):
    if a > 10**18 or a == 0:
        break
    else:
        a = a*i
        
    
    
if a> 10**18:
    print('-1')
else :
    print(a)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC66 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
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()))
def f(a, b):
    if b == 0: 
        return 1
    if b % 2 == 0:
        d = f(a, b // 2)
        return d * d % mod
    if b % 2 == 1:
        return (a * f(a, b - 1)) % mod


def comb(n,r):
    if n - r < 0:
        return 0
    return fact[n] * invfact[r] * invfact[n-r] % mod

n = I()
a = LI()
cnt = [0]*(n+1)
for i in range(n+1):
    if cnt[a[i]]:
        a = cnt[a[i]]
        b = i+1
        break
    else:
        cnt[a[i]] = i+1

fact = [1]*(n+2)
invfact = [1]*(n+2)
for i in range(1,n+2):
    fact[i] = i*fact[i-1]
    invfact[i] = invfact[i-1] * f(i,mod-2) % mod
    
for i in range(n+1):
    res = 0
    res = (res + comb(n+1,i+1)) % mod
    res = (res - comb((a-1)+(n+1-b),i)) % mod
    print(res)
    

### FIXED CODE ###

#!/usr/bin/env python3
#ABC66 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
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()))
def f(a, b):
    if b == 0: 
        return 1
    if b % 2 == 0:
        d = f(a, b // 2)
        return d * d % mod
    if b % 2 == 1:
        return (a * f(a, b - 1)) % mod


def comb(n,r):
    if n - r < 0:
        return 0
    return fact[n] * invfact[r] * invfact[n-r] % mod

n = I()
a = LI()
cnt = [0]*(n+1)
for i in range(n+1):
    if cnt[a[i]]:
        a = cnt[a[i]]
        b = i+1
        break
    else:
        cnt[a[i]] = i+1

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

for i in range(n+1):
    res = 0
    res = (res + comb(n+1,i+1)) % mod
    res = (res - comb((a-1)+(n+1-b),i)) % mod
    print(res)
### BUGGY CODE ###

def lcm(x,y):
    for i in range(1,10**9):
        if i%x==0:
            if i%y==0:
                return(i)
                break

A,B=map(int,input().split())
print(lcm(A,B))

### FIXED CODE ###

def gcd(x,y):
    while y!=0:
        x,y=y,x%y
    return x

def lcm(x,y):
    return x*y/gcd(x,y)

A,B=map(int,input().split())
print(int(lcm(A,B)))
### BUGGY CODE ###


a,b,n=map(int,input().split())
ans=0
for i in range(1,n+1):
  c=int(a*i/b)-a*int(i/b)
  ans=max(ans,c)
print(ans)

### FIXED CODE ###

import math
a,b,n=map(int,input().split())
ans=0
if b>n:
  ans=math.floor(a*n/b)
else:
  
  ans=math.floor(a*(b-1)/b)
print(ans)
### BUGGY CODE ###

from itertools import combinations
N = int(input())
L = sorted(list(map(int,input().split())))
ans = 0
for idx in range(2,N):
  if L[idx] < L[idx-1] + L[idx-2]:
    for cmb in combinations(L[:idx],2):
      if L[idx] < sum(cmb): ans += 1
print(ans)

### FIXED CODE ###

import bisect 
N = int(input())
L = sorted(list(map(int,input().split())))
ans = 0
for i in range(N-2):
  for j in range(i+1,N-1):
    idx = bisect.bisect(L,L[i]+L[j]-1)
    ans += idx-j-1
print(ans)
### BUGGY CODE ###

from collections import deque
n,m=map(int,input().split())
f=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    if not (b-1) in f[a-1]:
        f[a-1].append(b-1)
    if not (a-1) in f[b-1]:
        f[b-1].append(a-1)
chk=[False]*n
q=deque()
ans=0
for i in range(n):
    if chk[i]==True:
        continue
    q.append(i)
    chk[i]=True
    cnt=1
    while q:
        x=q.popleft()
        for nx in f[x]:
            if chk[nx]==True:
                continue
            q.append(nx)
            chk[nx]=True
            cnt+=1
    ans=max(ans,cnt)
print(ans)

### FIXED CODE ###

def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]
    n,m=map(int,input().split())
    f=[set() for _ in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        f[a-1].add(b-1)
        f[b-1].add(a-1)
    chk=[False]*n
    q=[]
    ans=0
    for i in range(n):
        if chk[i]==True:
            continue
        q.append(i)
        chk[i]=True
        cnt=1
        while q:
            x=q.pop()
            for nx in f[x]:
                if chk[nx]==True:
                    continue
                q.append(nx)
                chk[nx]=True
                cnt+=1
        ans=max(ans,cnt)
    print(ans)

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

def main():
    h,w = map(int,input().split())
    a = {}
    for i in range(h):
        a[i] = input()
    ans = 0
    L = []
    R = []
    D = []
    U = []
    for x in range(h):
        L.append([])
        R.append([])
        for y in range(w):
            if a[x][y] == "#":
                L[x].append(0)
            elif y == 0:
                L[x].append(1)
            else:
                L[x].append(L[x][y-1]+1)
        for y in range(w-1,-1,-1):
            if a[x][y] == "#":
                R[x].append(0)
            elif y == w-1:
                R[x].append(1)
            else:
                R[x].append(R[x][w-y-2]+1)
        R[x].reverse()
    for y in range(w):
        D.append([])
        U.append([])
        for x in range(h):
            if a[x][y] == "#":
                U[y].append(0)
            elif x == 0:
                U[y].append(1)
            else:
                U[y].append(U[y][x-1]+1)
        for x in range(h-1,-1,-1):
            if a[x][y] == "#":
                D[y].append(0)
            elif x == h-1:
                D[y].append(1)
            else:
                D[y].append(D[y][h-x-2]+1)
        D[y].reverse()

    for x in range(h):
        for y in range(w):
            ans = max(ans, R[x][y]+L[x][y]+U[y][x]+D[y][x]-3)
            
    print(ans)
main()

### FIXED CODE ###

def main():
    h,w = map(int,input().split())
    a = {}
    for i in range(h):
        a[i] = input()
    ans = 0
    L = []
    R = []
    D = []
    U = []
    for x in range(h):
        L.append([])
        R.append([])
        for y in range(w):
            if a[x][y] == "#":
                L[x].append(0)
            elif y == 0:
                L[x].append(1)
            else:
                L[x].append(L[x][y-1]+1)
        for y in range(w-1,-1,-1):
            if a[x][y] == "#":
                R[x].append(0)
            elif y == w-1:
                R[x].append(1)
            else:
                R[x].append(R[x][w-y-2]+1)
        R[x].reverse()
    for y in range(w):
        D.append([])
        U.append([])
        for x in range(h):
            if a[x][y] == "#":
                U[y].append(0)
            elif x == 0:
                U[y].append(1)
            else:
                U[y].append(U[y][x-1]+1)
        for x in range(h-1,-1,-1):
            if a[x][y] == "#":
                D[y].append(0)
            elif x == h-1:
                D[y].append(1)
            else:
                D[y].append(D[y][h-x-2]+1)
        D[y].reverse()

    for x in range(h):
        for y in range(w):
            ans = max(ans, R[x][y]+L[x][y]+U[y][x]+D[y][x]-3)
            
    print(ans)
main()
### BUGGY CODE ###

import numpy as np
from copy import deepcopy
from heapq import heappop, heappush
from bisect import bisect_left, bisect
from collections import Counter, defaultdict, deque
from itertools import product, permutations, combinations

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

sum = 0
for c in combinations(A, 2):
    sum += c[0] * c[1]

print(sum % (10**9 + 7))
exit()


### FIXED CODE ###

import numpy as np
from copy import deepcopy
from heapq import heappop, heappush
from bisect import bisect_left, bisect
from collections import Counter, defaultdict, deque
from itertools import product, permutations, combinations

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

s = 0

S = [0]

for i in range(N):
    S.append(A[i] + S[i])

for i in range(N):
    s += A[i] * S[i]

print(s % (10**9 + 7))
exit()
### BUGGY CODE ###

N, M, Q = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
PQ = [list(map(int, input().split())) for _ in range(Q)]

#X[l][r]はlからrをちょうど走る電車の数
X = [[0 for _ in range(N+1)] for _ in range(N+1)]
for l, r in LR:
    X[l][r] += 1
cum = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, N+1):
        cum[i][j] = cum[i][j-1] + X[i][j]

for p, q in PQ:
    ans = 0
    for i in range(p, q+1):
        ans += cum[i][q] - cum[i][p-1]
    print(ans)

### FIXED CODE ###

N, M, Q = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
PQ = [list(map(int, input().split())) for _ in range(Q)]

#X[l][r]はlからrをちょうど走る電車の数
X = [[0 for _ in range(N+1)] for _ in range(N+1)]
for l, r in LR:
    X[l][r] += 1
cum = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, N+1):
        cum[i][j] = cum[i][j-1] + X[i][j]

for p, q in PQ:
    ans = 0
    for i in range(p, q+1):
        ans += cum[i][q] - cum[i][p-1]
    print(ans)
### BUGGY CODE ###

N = int(input())
a = [ int(input()) for i in range(N) ]
ans = [1]*N
for i,x in enumerate(a):
  if i == N-1:
    ans[i]=max(a[:i])
  else:
    ans[i]=max(max(a[:i],a[i+1:]))
    
for i in range(N):
  print(ans[i])

### FIXED CODE ###

N = int(input())
a = [ int(input()) for i in range(N) ]

max_a = max(a)
sec_max_a = sorted(a)[-2]
ans = [max_a]*N
max_index = []
for i in range(N):
  if a[i] == max_a:
    max_index.append(i)
#print(max_index)

for i in max_index:
  ans[i] = sec_max_a
for i in ans:
  print(i)
### BUGGY CODE ###

import fractions
N = int(input())
As = list(map(int, input().split()))
As.sort()
ans = 1

for i in range(N):
    flag = True
    if i == 0:
        a = As[1]
    else:
        a = As[0]
    for j in range(N):
        if j != i:
            a = fractions.gcd(a, As[j])
            if a <= ans:
                flag = False
                break
    if flag:
        ans = a
print(ans)
        

### FIXED CODE ###

import fractions
import collections
N = int(input())
As = list(map(int, input().split()))
lgcd = [As[0]]
rgcd = collections.deque([As[-1]])
l = As[0]
r = As[-1]
for i in range(1, N):
    l = fractions.gcd(l, As[i])
    r = fractions.gcd(r, As[-(i+1)])
    lgcd.append(l)
    rgcd.appendleft(r)
ans = [lgcd[N-2], rgcd[1]]
for i in range(1, N-1):
    ans.append(fractions.gcd(lgcd[i-1], rgcd[i+1]))
print(max(ans))
### BUGGY CODE ###

x = input()
l = len(x)
for _ in range(l):
    x = x.replace('01', '')
    x = x.replace('10', '')
print(l - len(x))


### FIXED CODE ###

x = input()
l = len(x)
l0 = sum([1 for c in x if c == '1'])
l1 = l - l0
if l1 < l0:
    print(l - l0 + l1)
else:
    print(l - l1 + l0)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
from heapq import *
x, y, z, k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

a = sorted(a, reverse = True)
b = sorted(b, reverse = True)
c = sorted(c, reverse = True)

ans = [[-(a[0] + b[0] + c[0]), 1, 1, 1]]
heapify(ans)
log = [[[0] * z for i in range(y)] for j in range(x)]
log[0][0][0] = 1

d = [(1, 0, 0), (0, 1, 0), (0, 0, 1)]
for i in range(k):
    temp, s, t, u = heappop(ans)
    temp = temp * (-1)
    print(temp)
    for ds, dt, du in d:
        ns = s + ds
        nt = t + dt
        nu = u + du
        if not(0 <= ns <= x and 0 <= nt <= y and 0 <= nu <= z):continue
        if log[ns - 1][nt - 1][nu - 1]:continue
        heappush(ans, [-(a[ns - 1] + b[nt - 1] + c[nu - 1]), ns, nt, nu])
        log[ns - 1][nt - 1][nu - 1] = 1


### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

c = sorted(c, reverse=True)
ab = []
for i in range(x):
    for j in range(y):
        temp = a[i] + b[j]
        ab.append(temp)

ab = sorted(ab, reverse=True)
ans = []
for i in range(z):
    for j in range(min(x * y, k)):
        temp = c[i] + ab[j]
        ans += [temp]
ans = sorted(ans, reverse=True)

for i in range(k):
    print(ans[i])
### BUGGY CODE ###

NK = [int(i) for i in input().split(" ")]
list1 = [(int(i)+1)/2 for i in input().split(" ")]
list2 = []
for j in range(NK[0]-NK[1]+1):
    list2.append(sum(list1[j:j+NK[1]]))
        
print(max(list2))

### FIXED CODE ###

Input1 = [int(_) for _ in input().split(" ")]
Input2 = [(int(i)+1)/2 for i in input().split(" ")]

sum_ = sum(Input2[:Input1[1]])
Max = sum_
for j in range(Input1[0]-Input1[1]):
    sum_ = sum_-Input2[j]+Input2[j+Input1[1]]
    if Max  < sum_:
        Max = sum_
        
print(Max)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
ll = []
for i in range(q):
	l = list(map(int, input().split()))
	ll.append(l)
    
for i in ll:
  if i[0] in a:
    a = [i[1] if j == i[0] else j for j in a]
    print(sum(a))
  else:
    print(sum(a))

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = [list(map(int,input().split(" "))) for i in range(0,q)]

ans = sum(a)
anum = collections.Counter(a)

for i in range(q):
    x, y = b[i][0], b[i][1]
    ans += anum[x] * (y - x)
    anum[y] += anum[x]
    anum[x] = 0
    print(ans)
### BUGGY CODE ###

from bisect import*
def main():
    root=[[],[]]
    def search_higher(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect(ptr[0],key)
            if i!=len(ptr[0]):ret=ptr[0][i]
            ptr=ptr[1][i]
        i=bisect(ptr[0],key)
        if i!=len(ptr[0]):ret=ptr[0][i]
        return ret
    def search_lower(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect_left(ptr[0],key)
            if i:ret=ptr[0][i-1]
            ptr=ptr[1][i]
        i=bisect_left(ptr[0],key)
        if i:ret=ptr[0][i-1]
        return ret
    def insert_rec(ptr,key):
        b_size=64
        if not ptr[1]:
            insort(ptr[0],key)
            if len(ptr[0])==b_size*2-1:
                ret=[ptr[0][:b_size],[]]
                ptr[0]=ptr[0][b_size:]
                return ret
        else:
            i=bisect(ptr[0],key)
            tmp=insert_rec(ptr[1][i],key)
            if tmp:
                ptr[0].insert(i,tmp[0].pop())
                ptr[1].insert(i,tmp)
                if len(ptr[1])==b_size*2:
                    ret=[ptr[0][:b_size],ptr[1][:b_size]]
                    ptr[0],ptr[1]=ptr[0][b_size:],ptr[1][b_size:]
                    return ret
    def insert(key):
        tmp=insert_rec(root,key)
        if tmp:root[0],root[1]=[tmp[0].pop()],[tmp,root]
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    insert(0)
    insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(v)-v)*(v-search_lower(v))*i
        insert(v)
    print(c)
main()

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

X = int(input())
if X == 2:
  print(2)
  exit()

num = 3
ps = [2]
while 1:
  flag = True
  for p in ps:
    if num%p == 0:
      flag = False
      break
  if flag:
    ps.append(num)
    if num>=X:
      print(num)
      exit()
  num += 1

### FIXED CODE ###

X = int(input())
if X == 2:
  print(2)
  exit()

num = 3
ps = [2]
while 1:
  flag = True
  for p in ps:
    if num%p == 0:
      flag = False
      break
  if flag:
    ps.append(num)
    if num>=X:
      print(num)
      exit()
  num += 2
### BUGGY CODE ###

S = input().rstrip('\r\n')
Q = int(input())
for _ in range(Q):
    query = input().rstrip('\r\n')
    t, f, c = '', '', ''
    if len(query) == 1:
        t = query
    else:
        t, f, c = query.split(' ')
    if t == '1':
        S = S[::-1]
    else:
        if f == '1':
            S = c + S
        else:
            S = S + c
print(S)

### FIXED CODE ###

from collections import deque

S = input().rstrip('\r\n')
S_list = deque(S)
is_reverse = False

Q = int(input())
for _ in range(Q):
    query = input().rstrip('\r\n')
    t, f, c = '', '', ''
    if len(query) == 1:
        t = query
    else:
        t, f, c = query.split(' ')
    if t == '1':
        is_reverse = not is_reverse
    else:
        if f == '1':
            if is_reverse:
                S_list.append(c)
            else:
                S_list.appendleft(c)
        else:
            if is_reverse:
                S_list.appendleft(c)
            else:
                S_list.append(c)
if is_reverse:
    S_list.reverse()
print(''.join(S_list))
### BUGGY CODE ###

MOD=1000000007
N=input()
A=list(map(int,input().split()))
l=len(A)
s=0
for i in range(l):
    for j in range(i+1,l):
        s+=A[i]*A[j]
print(s%MOD)

### FIXED CODE ###

MOD=1000000007
N=input()
A = list(map(int,input().split()))
l=len(A)
s=0
B=sum(A)
for i in range(l):
    B-=A[i]
    s+=A[i]*B
print(s%MOD)