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

txt = input()
n = (int)(input())
for i in range(n):
  temp = input()
  if temp[0] == '1':
    txt = txt[::-1]
  else:
    sec, moji = (int)(temp.split(" ")[1]), temp.split(" ")[2]
    if sec == 1:
      txt = moji + txt
    else:
      txt += moji
print(txt)    

### FIXED CODE ###

txt = input()
n = (int)(input())
count = 0
sentou = ""
saigo = ""
for i in range(n):
  temp = input()
  if temp[0] == '1':
    count += 1
  else:
    sec, moji = (int)(temp.split(" ")[1]), temp.split(" ")[2]
    if (sec + count) % 2 == 1:
      sentou = moji + sentou
    else:
      saigo += moji
if count % 2 == 1:
  txt = saigo[::-1] + txt[::-1] + sentou[::-1]
else:
  txt = sentou + txt + saigo
print(txt)
### BUGGY CODE ###

import numpy as np

n, d, a = map(int,input().split())
xh = np.zeros((n,2), dtype = int)
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]

num = 0
xh = xh[np.argsort(xh[:, 0])]

while xh.size > 0.5:
    if xh[0,1]%a == 0:
        nat = int((xh[0,1])/a)
    else:
        nat = int((xh[0,1])/a+1)
    num += nat
    dam = nat*a
    for i in range(xh.shape[0]):
        if xh[i,0] <= xh[0,0]+2*d:
            xh[i,1] -= dam
        else:
            break
    while xh[0,1] < 0.5:
        xh = np.delete(xh, 0, 0)
        if xh.size == 0:
            break
    if xh.size == 0:
        break

print(num)


### FIXED CODE ###

import math

n, d, a = map(int,input().split())
xh = [[0 for i in range(2)] for j in range(n)]
left = [i for i in range(n)]
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]

num = 0
xh.sort(key=lambda xh:xh[0])

for i in range(n):
    for j in range(left[i-1],i):
        if xh[j][0]+d >= xh[i][0]-d:
            left[i] = j
            break

dam = [0]*n

def dsum(k):
    if k == 0:
        return 0
    elif left[k] == 0:
        return dam[k-1]
    else:
        return dam[k-1]-dam[left[k]-1]

for i in range(n):
    res = xh[i][1]-dsum(i)
    nat = max([math.ceil(res/a),0])
    dam[i] = dam[i-1]+a*nat
    if res > 0:
        num += nat

print(num)
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
ans = 0
for i in range(N):
    P_j = P[:i]
    if P_j == []:
        ans += 1
    elif min(P_j) >= P[i]:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
P_min = [2*(10**5)]
for i in range(N-1):
    P_min.append(min(P_min[i],P[i]))
ans = 0
for i in range(N):
    if P_min[i] >= P[i]:
        ans += 1
print(ans)
### BUGGY CODE ###

#D

h,w = (int(x) for x in input().split())

s = []
for i in range(h):
    x = input()
    s.append(x)

y = [[0] * w for i in range(h)]
t = [[0] * w for i in range(h)]

#横
for i in range(h):
    mi = -1
    count = 0
    for j in range(w):
        this_s = s[i][j]
        
        if this_s == ".":
            count += 1
            if mi == -1:
                mi = j
        if this_s == "#" and not(mi == -1):
            y[i][mi:j] = [count] * (j-mi)
            mi = -1
            count = 0
    else:
        if not(mi == -1):
            y[i][mi:w] = [count] * (w-mi)
#print(y)
        
#縦
for j in range(w):
    mi = -1
    count = 0
    for i in range(h):
        this_s = s[i][j]
        
        if this_s == ".":
            count += 1
            if mi == -1:
                mi = i
        if this_s == "#" and not(mi == -1):
            for k in range(mi,i):
                t[k][j] = count
            mi = -1
            count = 0
    else:
        if not(mi == -1):
            #t[mi:h][j] = [count] * (h-mi)
            for k in range(mi,h):
                t[k][j] = count
#print(t)

count = 0
for i in range(h):
    for j in range(w):
        this_count = y[i][j] + t[i][j] -1
        count = max(count, this_count)
        
print(count)


### FIXED CODE ###

#D

h,w = (int(x) for x in input().split())

s = []
for i in range(h):
    x = input()
    s.append(x)

y = [[0] * w for i in range(h)]
t = [[0] * w for i in range(h)]

#横
for i in range(h):
    mi = -1
    count = 0
    for j in range(w):
        this_s = s[i][j]
        
        if this_s == ".":
            count += 1
            if mi == -1:
                mi = j
        if this_s == "#" and not(mi == -1):
            y[i][mi:j] = [count] * (j-mi)
            mi = -1
            count = 0
    else:
        if not(mi == -1):
            y[i][mi:w] = [count] * (w-mi)
#print(y)
        
#縦
for j in range(w):
    mi = -1
    count = 0
    for i in range(h):
        this_s = s[i][j]
        
        if this_s == ".":
            count += 1
            if mi == -1:
                mi = i
        if this_s == "#" and not(mi == -1):
            for k in range(mi,i):
                t[k][j] = count
            mi = -1
            count = 0
    else:
        if not(mi == -1):
            #t[mi:h][j] = [count] * (h-mi)
            for k in range(mi,h):
                t[k][j] = count
#print(t)

count = 0
for i in range(h):
    for j in range(w):
        this_count = y[i][j] + t[i][j] -1
        count = max(count, this_count)
        
print(count)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
MOD = 10**9 + 7
for i in range(60):
    tmp0 = 0
    tmp1 = 0
    for j in range(n):
        if a[j]>>i&1 == 0: tmp0 += 1
        else: tmp1 += 1
    ans += (tmp0*tmp1%MOD)*(2**i%MOD)
print(ans%MOD)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
MOD = 10**9 + 7
for i in range(60):
    tmp0 = 0
    tmp1 = 0
    for j in range(n):
        if a[j]>>i&1 == 0: tmp0 += 1
        else: tmp1 += 1
    ans += (tmp0*tmp1%MOD)*(2**i%MOD)
print(ans%MOD)
### BUGGY CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
d[~w+a*w+b]=1
q=[(a-1,b-1)]
for s,t in q:
 p=d[s*w+t]+1
 for y,x in(1,0),(-1,0),(0,-1),(0,1):
  for z in range(k):
   i,j=s+y*~z,t+x*~z
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[i*w+j]<p:break
   q+=(i,j),;d[i*w+j]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n,q=map(int,input().split())
edges=[[] for i in range(n)]
for i in range(n-1):
    a,s=map(int,input().split());a-=1;s-=1
    edges[a].append(s)
    edges[s].append(a)
cnt=[-1]*n
add=[0]*n
for _ in range(q):
    a,s=map(int,input().split())
    add[a-1]+=s

def f(x):
    if cnt[x]!=-1:return cnt[x]
    ret=add[x]
    after=[]
    for to in edges[x]:
        if cnt[to]==-1:after.append(to)
        else:ret+=cnt[to]
    cnt[x]=ret
    for i in after:
        f(i)
    return 0
f(0)
print(*cnt,sep=" ")

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n,q=map(int,input().split())
cnt=[0]*(n)
edges=[0]*n
for i in range(n):
    edges[i]=[]
for i in range(n-1):
    a,s=map(int,input().split())
    edges[a-1].append(s-1);edges[s-1].append(a-1)

from collections import deque
dq=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
for i in range(q):
    p,x=map(int,input().split())
    cnt[p-1]+=x

for i in edges[0]:
    dq.append((0,i))
while dq:
    f,t=dq.popleft()
    cnt[t]+=cnt[f]
    for to in edges[t]:
        if to!=f:dq.append((t,to))
    
print(*cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
cnt = 0
for i in range(n):
    if b[i] > 0:
        while a[i] > 0:
            if b[i] == 0:
                break
            a[i] -= 1
            b[i] -= 1
            cnt += 1
        while a[i+1] > 0:
            if b[i] == 0:
                break
            a[i+1] -= 1
            b[i] -= 1
            cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ans = 0
for i in range(n):
    if a[i] >= b[i]:
        ans += b[i]
    else:
        ans += a[i]
        b[i] -= a[i]
        if a[i+1] >= b[i]:
            ans += b[i]
            a[i+1] -= b[i]
        else:
            ans += a[i+1]
            a[i+1] = 0
print(ans)
### BUGGY CODE ###

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

if ((b-a)+1 >= 2*k):
   c = [x for x in range(a, b+1)]
   for i in range(0, k):
      print(c[i])
   for i in reversed(range(1, k+1)):
      print(c[-i])
else:
   c = [print(x) for x in range(a, b+1)]


### FIXED CODE ###

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

if ((b-a)+1 >= 2*k):
   c1 = [print(x) for x in range(a, a+k)]
   c2 = [x for x in reversed(range(b+1-k, b+1))]
   c2.sort()
   for i in c2:
      print(i)
else:
   c = [print(x) for x in range(a, b+1)]
### BUGGY CODE ###

import sys

n,m = map(int,input().split())

li = [list(map(int,input().split())) for i in range(m)]

for i in range(m-1):
    for j in range(i+1,m):
        s = set(li[i]) | set(li[j])
        if 1 in s and n in s and len(s) == 3:
            print("POSSIBLE")
            sys.exit()
print("IMPOSSIBLE")


### FIXED CODE ###

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

sa = set()
sb = set()

for i in range(M):
    a,b = map(int,input().split())
    if a==1 : sb.add(b)
    if b == N : sa.add(a)
    
print("IMPOSSIBLE" if len(sa&sb) == 0 else "POSSIBLE")
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter 
from collections import defaultdict 
def main():
    s = input() 
    s = ''.join(reversed(s))
    n = len(s)
    T = [0]
    dd = defaultdict(int) 
    dd[0] += 1
    for i in range(n):
        T.append((int(s[i])*10**i+T[i])%2019)
        dd[(int(s[i])*10**i+T[i])%2019] += 1
    ans = 0
    for i in dd.values():
        ans += i*(i-1)//2
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter 
from collections import defaultdict 

def main():
    s = input() 
    n = len(s)
    T = [0]
    P = 2019
    dd = defaultdict(int) 
    dd[0] += 1
    for i in range(1, n+1):
        x = (int(s[-i])*pow(10, i-1, P) + T[i-1])%P
        T.append(x)
        dd[x] += 1
    ans = 0
    for i in dd.values():
        ans += i*(i-1)//2
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

s=str(0)+input()
t=str(0)+input()

dp=[[0]*(len(t)) for i in range(len(s))]

for i in range(1,len(s)):
    for j in range(1,len(t)):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])

ans=[""]*dp[i][j]
i=len(s)-1
j=len(t)-1
k=dp[i][j]-1
while i>0 and j>0:
    if s[i]==t[j]:
        ans[k]=s[i]
        k-=1
        i-=1
        j-=1
    elif dp[i][j]==dp[i-1][j]:i-=1
    elif dp[i][j]==dp[i][j-1]:j-=1

print("".join(ans))

### FIXED CODE ###

s=str(0)+input()
t=str(0)+input()

dp=[[0]*(len(t)) for i in range(len(s))]

for i in range(1,len(s)):
    for j in range(1,len(t)):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])

ans=[""]*dp[i][j]
i=len(s)-1
j=len(t)-1
k=dp[i][j]-1
while i>0 and j>0:
    if s[i]==t[j]:
        ans[k]=s[i]
        k-=1
        i-=1
        j-=1
    elif dp[i][j]==dp[i-1][j]:i-=1
    elif dp[i][j]==dp[i][j-1]:j-=1

print("".join(ans))
### BUGGY CODE ###

n=int(input())
t,a=map(int,input().split())
ln=[int(h) for h in input().split()]
ln = sorted(ln)
i=0
for h in ln:
    while (t-h*0.006)<=a:
        i+=1
print(min(ln[i],ln[i+1]).index())

### FIXED CODE ###

n=int(input())
t,a=map(int,input().split())
ln=[int(x) for x in input().split()]
ans=[abs(t-0.006*x-a)  for x in ln]
print(ans.index(min(ans))+1)
### BUGGY CODE ###

N=int(input())

sum_=0
tmp=[0 for _ in range(20)]
A =list(map(int,input().split()))
i=0
biA=[[] for _ in range(N)]
ans=0
for j in range(N):
    k=0
    while A[j]!=0:
        biA[j].append(A[j]%2)
        A[j]//=2
        k+=1
    for k,x in enumerate(biA[j]):
        tmp[k]+=x
    while 2 in tmp:
        for k,x in enumerate(biA[i]):
            tmp[k]-=x
        i+=1
    ans+=j-i+1
print(ans)

### FIXED CODE ###

N=int(input())

sum_=0
A =list(map(int,input().split()))
j=0
ans=0
sum_=0
for i in range(N):
    k=0
    while j<N and sum_+A[j]==sum_^A[j]:
        sum_+=A[j]
        ans+=j-i+1
        j+=1
    sum_-=A[i]
print(ans)
### BUGGY CODE ###

import math

k = int(input())
cnt = 0

for l in range(1,k+1):
    for m in range(1,k+1):
        for n in range(1,k+1):
            tmp = math.gcd(l,m)
            if tmp == 1:
                cnt += 1
            else:
                cnt += math.gcd(tmp,n)
            
print(cnt)

### FIXED CODE ###

#C

import math

k = int(input())
cnt = 0

for i in range(1,k+1):
    for j in range(i,k+1):
        tmp = math.gcd(i,j)
        for l in range(1,k+1):
            if i != j:
                cnt += 2 * math.gcd(tmp,l)
            else:
                cnt += math.gcd(tmp,l)
            
print(cnt)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(S[l-1:r].count('AC'))

for i in ans:
    print(i)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

t = [0] * N
t[0] = 0
for i in range(1,N):
    if S[i-1] == 'A' and S[i] == 'C':
        t[i] = t[i-1] + 1
    else:
        t[i] = t[i-1]

ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(t[r-1] - t[l-1])

for a in ans:
    print(a)
### BUGGY CODE ###

INT_MAX = 10**8
h, n = map(int, input().split())
e = [tuple(map(int, input().split())) for _ in range(n)]

dp = [INT_MAX] * (h+1)
dp[0] = 0
for i in range(1, h+1):
  for a, b in e:
    c = dp[max(0, i - a)] + b
    dp[i] = min(dp[i], c)

print(dp[h])

### FIXED CODE ###

INT_MAX = 10**8
h, n = map(int, input().split())
e = tuple(tuple(map(int, input().split())) for _ in range(n))

dp = [INT_MAX] * (h+1)
dp[0] = 0
for i in range(1, h+1):
  for a, b in e:
    c = dp[max(0, i - a)] + b
    dp[i] = min(dp[i], c)

print(dp[h])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(202020)

n, q = map(int, input().split())
to = [[] for _ in range(n)]
score = [0 for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    to[a].append(b)
    to[b].append(a)
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    score[p] += x

visited = [False for _ in range(n)]
def dfs(v, p=-1):
    for u in to[v]:
        if visited[u]:
            continue
        visited[v] = True
        score[u] += score[v]
        dfs(u, p=v)

dfs(0)
print(*score)

### FIXED CODE ###

N,Q=map(int, input().split())
node_lst=[list(map(int, input().split())) for i in range(N-1)]
ope_lst=[list(map(int, input().split())) for i in range(Q)]
cnt_lst=[0 for i in range(N)]
for ope in ope_lst:
    p, x = ope[0], ope[1]
    cnt_lst[p-1]+=x
node_lst=sorted(node_lst, key=lambda x:x[0])
for l in node_lst:
    src, dst = l[0]-1, l[1]-1
    cnt_lst[dst]+=cnt_lst[src]
print(" ".join([str(c) for c in cnt_lst]))
### BUGGY CODE ###

from operator import mul
from functools import reduce

while True:
	N = int(input())
	if N>=2 and N<=10**5:break

while True:
	num = list(map(int, input().split()))
	if N==len(num):break

#print(num)
ans = reduce(mul,num)
if ans > 10**18:
	print(-1)
else:
	print(ans)


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))
    if 0 in a: 
        print(0)
        return
    ans = 1
    for ai in a:
        ans *= ai
        if ans > 10**18:
            print(-1)
            return
    print(ans)
    
if __name__ =="__main__":
    main()
### BUGGY CODE ###

N,M =map(int,input().split())
A = [0]*N
B = [0]*M
C = [0]*M
ans = int(0)

A = list(map(int, input().split()))
D = A
for i in range(M):
    B[i],C[i] = list(map(int,input().split()))
    for j in range(B[i]):
        D.append(C[i])

D.sort()

S = int(N)

for i in range(M):
    S +=B[i]

for i in range(S-1,S-N-1,-1):
    ans += D[i]

print(ans)

### FIXED CODE ###

from heapq import heappush, heappop

# input
N,M =map(int,input().split())
A = [0]*N
B = [0]*M
C = [0]*M

A = list(map(int, input().split()))
A.sort()
for i in range(M):
    B[i],C[i] = list(map(int,input().split()))


def solve():

    pairs = zip(C, B)
    sortedpairs = sorted(pairs, key=lambda x: x[0])
    for i in range(M):
        B[i]=sortedpairs[i][1]
        C[i]=sortedpairs[i][0]

    ansA=[0]*N
    for j in range(N):
        ansA[j] = A[j]

    p = int(0)
    j = int(0)
    while  j<N and M>=1+p :
        jd = int(0)
        if ansA[j] >= C[M - 1 - p]:
            break
        while  B[M-1-p]-jd>0 :
            if j==N : break
            if ansA[j]>=C[M-1-p] :
                break
            else:
                ansA[j]=C[M-1-p]
            jd +=1
            j +=1

        p +=1

    ans = int(0)
    for j in range(N):
        ans += ansA[j]

    print(ans)

solve()
### BUGGY CODE ###

h,w=map(int,input().split())
s=set()
a=[]
from collections import deque
q=deque([])
for i in range(h):
    tmp=list(input())
    a.append(tmp)
    for j in range(w):
        if tmp[j]=="#":
            q.append((i,j,0))

ans=0
ll=[[0,1],[0,-1],[1,0],[-1,0]]
while q:
    x,y,v=q.popleft()
    ans=max(ans,v)
    for i,j in ll:
        if 0<=x+i<h and 0<=y+j<w and a[i+x][j+y]==".":
            a[i+x][j+y]="#"
            q.append((i+x,j+y,v+1))

print(ans)





### FIXED CODE ###

h,w=map(int,input().split())
s=set()
a=[]
from collections import deque
q=deque([])
for i in range(h):
    tmp=list(input())
    a.append(tmp)
    for j in range(w):
        if tmp[j]=="#":
            q.append((i,j,0))

ans=0
ll=[[0,1],[0,-1],[1,0],[-1,0]]
while q:
    x,y,v=q.popleft()
    ans=max(ans,v)
    for i,j in ll:
        if 0<=x+i<h and 0<=y+j<w and a[i+x][j+y]==".":
            a[i+x][j+y]="#"
            q.append((i+x,j+y,v+1))

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

N, trans = int(input()), [int(input()), int(input()), int(input()), int(input()), int(input())]

persons = [N, 0, 0, 0, 0, 0]

t = 0
while persons[5] != N:
    for i in reversed(list(range(0, 5))):
        if persons[i] > 0:
            np = trans[i] if persons[i] >= trans[i] else persons[i]            
            persons[i] -= np
            persons[i+1] += np
    t += 1    

print(t)

### FIXED CODE ###

N, trans = int(input()), [int(input()), int(input()), int(input()), int(input()), int(input())]

min_trans = min(trans)
print(int((N-1)/min_trans) + 1 + 4)
### BUGGY CODE ###

# coding: utf-8
N = int(input())
A = list(map(int, input().split()))
sorted_A = sorted(A)
ans = 0
l = []
if 1 not in A:
    print(-1)
    exit()

i = 0
while True:
    if A == sorted_A:
        print(N - len(set(A)))
        exit()
        break
    if A[i] > sorted_A[i]:
        tmp = A[i]
        A.remove(tmp)
        sorted_A.remove(tmp)
        continue
    i += 1

### FIXED CODE ###

# coding: utf-8
N = int(input())
A = list(map(int, input().split()))
if 1 not in A:
    print(-1)
    exit()

target = 1
idx = 0
ans = 0
while idx < len(A):
    if A[idx] == target:
        target += 1
        ans += 1
    idx += 1
print(N - ans)
### BUGGY CODE ###

M=998244353
n,s,*l=map(int,open(0).read().split())
dp=[[0]*(s+1) for _ in '01']
dp[0][0]=1
b=0
for i in range(n):
  b^=1
  for j in range(s+1):
    dp[b][j]=dp[b^1][j]*2%M
    if j>=l[i]: dp[b][j]+=dp[b^1][j-l[i]]
print(dp[n%2][s]%M)

### FIXED CODE ###

M=998244353
n,s,*l=map(int,open(0).read().split())
dp=[[0]*(s+1) for _ in '01']
dp[0][0]=1
b=0
for i in range(n):
  b^=1
  for j in range(s+1):
    dp[b][j]=dp[b^1][j]*2
    if j>=l[i]: dp[b][j]+=dp[b^1][j-l[i]]
    dp[b][j]%=M
print(dp[n%2][s])
### BUGGY CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)


### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit, maxsize


def main(readline=stdin.readline):
    n, q = (int(s) for s in readline().split())

    base = [0] * n

    for i in range(q):
        a, v = (int(s) for s in readline().split())
        base[a-1] += v

        index = value = -maxsize
        for i, v in enumerate(base, 1):
            if value < v:
                value = v
                index = i
        print(index, value)
    exit()


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def main(readline=stdin.readline):
    n, q = (int(s) for s in readline().split())

    base = [0] * n
    midway = [0] * (n//100 + 1)
    last = [0] * (n//10000 + 1)

    for _ in range(q):
        a, v = (int(s) for s in readline().split())

        a -= 1
        base[a] += v

        b = a - a % 100

        index = b
        value = base[b]
        end = b + 100 if b + 100 < n else n
        for i in range(b, end):
            if value < base[i]:
                value = base[i]
                index = i
        midway[b//100] = index

        c = a - a % 10000
        cc = c // 100

        index = c
        value = base[c]
        for i in midway[cc:cc+100]:
            if value < base[i]:
                value = base[i]
                index = i
        last[c//10000] = index

        index = last[0]
        value = base[index]
        for i in last:
            if value < base[i]:
                value = base[i]
                index = i

        print(index+1, value)
    exit()


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

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

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
MOD = 1000000007
S = sum(A) % MOD
ans = 0

for x in A:
    S -= x
    S %= MOD
    ans += S * x
    ans %= MOD
ans %= MOD
print(ans)