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

N = int(input())

A_list = list(map(int, input().split())) # case1 : [7, 6, 8]

def gcd(a, b):
    while b != 0:
        a, b = b, a%b
    return a

ans = 0

for i in range(N):
    left_gcd = 0
    right_gcd = 0

    for j in range(0, i):
        left_gcd = gcd(A_list[j], left_gcd)

    for k in range(i+1, N):
        right_gcd = gcd(A_list[k], right_gcd)

    i_gcd = gcd(left_gcd, right_gcd)

    if ans < i_gcd:
        ans = gcd(left_gcd, right_gcd)

print(ans)

### FIXED CODE ###

N = int(input())

A_list = list(map(int, input().split())) # case1 : [7, 6, 8]

def gcd(a, b):
    while b != 0:
        a, b = b, int(a%b)
    return a

left_gcd = [0] * (N+1)
right_gcd = [0] * (N+1)
for i in range(N):
    left_gcd[i+1] = gcd(A_list[i], left_gcd[i])
for i in range(N-1, 0, -1):
    right_gcd[i] = gcd(A_list[i], right_gcd[i+1])

ans = 0

for i in range(N):
    i_gcd = gcd(left_gcd[i], right_gcd[i+1])
    if ans < i_gcd:
        ans = i_gcd

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

import sys
sys.setrecursionlimit(10**6)

n= int(input())
s= input()

candidate = set()

def dfs(num,pw):
    global s
    global n
    global candidate
    if len(pw) == 3:
        candidate.add(pw)
        return
    elif num == n:
        return
    else:
        dfs(num+1,pw)
        pw+=s[num]
        dfs(num+1,pw)

dfs(0,"")

print(len(candidate))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n= int(input())
s= input()

sum=0

for i in range(10):
    ix = s.find(str(i))
    if ix == -1:
        continue
    six = s[ix+1:]
    for j in range(10):
        iy = six.find(str(j))
        if iy == -1:
            continue
        siy = six[iy+1:]
        for k in range(10):
            iz = siy.find(str(k))
            if iz >= 0:
                sum+=1
print(sum)
### BUGGY CODE ###

N=int(input())
S=input()
R=0

def judge(i,j,k):
  if j-i == k-j:
    # print(i,j,k, "false")
    return False
  else:
    if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
      # print(i,j,k, "true")
      return True
    else:
      # print(i,j,k, "false")
      return False

def main(R):
  for i in range(N):
    for j in range(i+1,N):
      for k in range(j+1,N):
        if judge(i,j,k):
          R+=1
  print(R)

main(R)

### FIXED CODE ###

n = int(input())
s = input()
result = 0

r = s.count('R')
g = s.count('G')
b = s.count('B')

result = r * g * b
count = 0

for i in range(n):
    for j in range(i, n):
        k = 2 * j - i
        if j < k < n:
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
                count += 1

print(result-count)
### BUGGY CODE ###

N, X = [int(x) for x in input().split(' ')]

city = [abs(int(x) - X) for x in input().split(' ')]
max_fact = city[0]

for x in city:
    while x!=0:
        if x > max_fact:
            x -= max_fact
        elif x == max_fact:
            break
        else:
            tmp = max_fact
            max_fact = x
            x = tmp
    if max_fact==1:
        break

print(max_fact)

### FIXED CODE ###

N, X = [int(x) for x in input().split(' ')]

city = [abs(int(x) - X) for x in input().split(' ')]
max_fact = city[0]

for x in city:
    while x!=0:
        x %= max_fact
        if x > 0:
            tmp = max_fact
            max_fact = x
            x = tmp
    if max_fact==1:
        break

print(max_fact)
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
while m>0:
    a[a.index(max(a))] //=2
    m-=1
print(sum(a))

### FIXED CODE ###

import heapq
n,m = map(int,input().split())
a = list(map(int,input().split()))
a = list(map(lambda x:x*(-1),a))
heapq.heapify(a)
while m>0:
    ma = heapq.heappop(a)*(-1)
    ma //=2
    heapq.heappush(a,ma*(-1))
    m-=1
print(sum(a)*(-1))
### BUGGY CODE ###

n = int(input())
lists = list(map(int,input().split()))
ans = 1
for i in range(n):
    ans *= lists[i]
print(ans if ans <= 10**18 else -1)

### FIXED CODE ###

n = int(input())
lists = list(map(int,input().split()))
ans = 1
if sorted(lists)[0] == 0:
    ans = 0
else:
    for i in range(n):
        ans *= lists[i]
        if ans > 10**18:
            ans = -1
            break
print(ans)
### BUGGY CODE ###

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

count = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            if a[i] < b[j] < c[k]:
                count += 1
print(count)        

### FIXED CODE ###

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

a = sorted(a)
b = sorted(b)
c = sorted(c)

import bisect
count = 0
for i in b:
    a_count = bisect.bisect_left(a, i)
    c_count = n - bisect.bisect_right(c, i)
    count += a_count * c_count
    
print(count)
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]


dp = [float("inf")] * N
dp[0] = 0

for i in range(1, N):

    dp[i] = min(
        [dp[i-k]+abs(h[i]-h[i-k]) for k in range(min(i+1, K+1))]
    )

print(dp[N-1])


### FIXED CODE ###

def main():
	N, K = map(int, input().split())
	h = list(map(int, input().split()))

	dp=[0]*N
 
	for i in range(1,N):
		dp[i] = min(
			dp[g] + abs(h[i] - h[g]) for g in range(max(i-K,0), i)
		)
	print(dp[N-1])
main()
### BUGGY CODE ###

mod = 10**9+7
S = input()
Q=0
DP=[[0]*3 for i in range(len(S))]#DP[x][y] x+1文字目までの
#y=0,1,2,3 = A,AB,ABC
if S[0] == "A" or S[0]=="?":
    DP[0] = [1,0,0]
    if S[0]=="?":
        Q=1
else:
    DP[0] = [0,0,0]
for i in range(1,len(S)):
    s = S[i]
    a,b,c = DP[i-1]
    if s=="A":
        DP[i]=[a+3**Q,b,c]
    elif s=="B":
        DP[i]=[a,a+b,c]
    elif s=="C":
        DP[i]=[a,b,b+c]
    else:
        DP[i]=[3**Q+3*a,a+3*b,b+3*c]
        Q+=1
    for j in range(3):
        DP[i][j]%=mod
print(DP[len(S)-1][2])

### FIXED CODE ###

mod = 10**9+7
S = list(input())
Thankyou = 1
DP=[]
#DP[x][y] x+1文字目までを見たときの、
#y=0,1,2 : A,AB,ABCの登場回数
if S[0] == "A" or S[0]=="?":
    DP.append([1,0,0])
    if S[0]=="?":
        Thankyou = 3
else:
    DP.append([0,0,0])
for i,s in enumerate(S):

    if i==0:continue
    a,b,c = DP[i-1]
    if s=="A":
        DP.append([(a+Thankyou)%mod,b,c])
    elif s=="B":
        DP.append([a,(a+b)%mod,c])
    elif s=="C":
        DP.append([a,b,(b+c)%mod])
    else:
        DP.append([(Thankyou+3*a)%mod,(a+3*b)%mod,(b+3*c)%mod])
        Thankyou *= 3
        Thankyou %= mod
print(DP[len(S)-1][2]%mod)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
Q=[]
a.sort()
t=0
for i in range(n):
    f=True
    if Q:
        for q in Q:
            if a[i]%q==0:
                f=False
                break
    if f and i<n-1 and a[i]==a[i+1]:
        f=False
        Q.append(a[i])
    if f:
        Q.append(a[i])
        t+=1
print(t)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
A.sort()
t=0
e=[True]*1000001
for i in range(n-1):
    a=A[i]
    if e[a]==False:
        continue
    b=a*2
    while b < 1000001:
        e[b]=False
        b+=a
    if A[i+1]==a:
        e[a]=False
for a in A:
    if e[a]:
        t+=1
print(t)
### BUGGY CODE ###

import heapq
N,M = map(int,input().split())
AB = []
for i in range(N):
    a,b = list(map(int,input().split()))
    AB.append([-b,a])
work = [0 for i in range(M)]
for i in range(1,M+1):
    AB2 = list(filter(lambda x:x[1]<=i,AB))
    heapq.heapify(AB2)
    if not AB2:
        continue
    b,a = heapq.heappop(AB2)
    work[i-1] = -b
    AB.remove([b,a])
print(sum(work))

### FIXED CODE ###

import heapq
from collections import defaultdict
N,M = map(int,input().split())
AB = defaultdict(list)
for i in range(N):
    a,b = list(map(int,input().split()))
    if a not in AB:
        AB[a] = [-b]
    else:
        AB[a] += [-b]
work = 0
AB2 = []
heapq.heapify(AB2)
for i in range(1,M+1):
    for j in AB[i]:
        heapq.heappush(AB2,j)
    if not AB2:
        continue
    b = heapq.heappop(AB2)
    work += -b
print(work)
### BUGGY CODE ###

h, w, k = map(int, input().split())
G = [[0]*w for _ in range(h)]
for _ in range(k):
  r, c, v = map(int, input().split())
  r -= 1
  c -= 1
  G[r][c] = v
dp = [[[0]*4 for i in range(w)] for j in range(h)]
dp[0][0][0] = 0
dp[0][0][1] = G[0][0]
for i in range(h):
  for j in range(w):
    if j:
      dp[i][j][0] = dp[i][j-1][0]
      for k in range(1, 4):
        dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1]+G[i][j], dp[i][j-1][k])
    if i:
      dp[i][j][0] = max(dp[i][j][0], max(dp[i-1][j]))
      dp[i][j][1] = max(dp[i][j][1], max(dp[i-1][j])+G[i][j])
ans = max(dp[h-1][w-1])
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

h, w, k = map(int, input().split())
G = [[0]*w for _ in range(h)]
for _ in range(k):
  r, c, v = map(int, input().split())
  r -= 1
  c -= 1
  G[r][c] = v
dp = [[[0]*w for i in range(h)] for j in range(4)]
dp[0][0][0] = 0
dp[1][0][0] = G[0][0]
for i in range(h):
  for j in range(w):
    if j:
      dp[0][i][j] = dp[0][i][j-1]
      for k in range(1, 4):
        dp[k][i][j] = max(dp[k][i][j], dp[k-1][i][j-1]+G[i][j], dp[k][i][j-1])
    if i:
      dp[0][i][j] = max(dp[0][i][j], max(dp[0][i-1][j],dp[1][i-1][j],dp[2][i-1][j],dp[3][i-1][j]))
      dp[1][i][j] = max(dp[1][i][j], max(dp[0][i-1][j],dp[1][i-1][j],dp[2][i-1][j],dp[3][i-1][j])+G[i][j])
ans = max(dp[0][h-1][w-1],dp[1][h-1][w-1],dp[2][h-1][w-1],dp[3][h-1][w-1])
print(ans)
### BUGGY CODE ###

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


counter = 0
for l in range(N):
    for r in range(l, N):
        if l == r:
            counter += 1
        else:
            sum_A = sum(A[l:r+1])
            k = l
            while k <= r:
                if k == l:
                    xor_A = A[k]
                else:
                    xor_A = xor_A ^ A[k]
                k += 1
            if sum_A == xor_A:
                counter += 1


print(counter)

### FIXED CODE ###

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

ans = 0
r = 0
xor_A = 0
for l in range(N):
    while (r < N and (xor_A ^ A[r]) == (xor_A + A[r])):
        xor_A += A[r]
        r += 1
    ans += r - l
    if l == r:
        r += 1
    else:
        xor_A -= A[l]
print(ans)
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(a,b+1):
  if i < a+k or b-k<i:
    print(i)

### FIXED CODE ###

a,b,k=map(int,input().split())
if b-a<2*k:
  for i in range(a,b+1):
    print(i)
  exit()
for i in range(a,a+k):
    print(i)
for i in range(b-k+1,b+1):
  print(i)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

N,M = map(int,input().split())
to = [[] for i in range(N)]
for i in range(N-1) :
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    to[u].append(v)
    to[v].append(u)

ans = [0]*N

def dfs(u, p) :
    for v in to[u] :
        if v == p :
            continue
        ans[v] += ans[u]
        dfs(v, u)

for i in range(M) :
    p,x = map(int,input().split())
    p -= 1
    ans[p] += x

dfs(0, -1)

print(*ans)


### FIXED CODE ###

from collections import deque

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

L = [[] for i in range(N)]
for i in range(N-1) :
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    L[u].append(v)
    L[v].append(u)

par = [-1]*N

cnt = [0]*N

for i in range(Q) :
    p,x = map(int,input().split())
    p -= 1
    cnt[p] += x

q = deque([0])
while len(q) :
    u = q.popleft()
    for v in L[u] :
        if v == par[u] :
            continue
        par[v] = u
        cnt[v] += cnt[u]
        q.append(v)


"""
for i in range(Q) :
    p,x = map(int,input().split())
    p -= 1
    q = deque([p])
    while len(q) :
        u = q.popleft()
        cnt[u] += x
        for v in L[u] :
            if v != par[u] :
                q.append(v)
"""
print(*cnt)
### BUGGY CODE ###

import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N = int(input())
A = list(map(int,(input().split())))
A.sort()
l = []
ans = 0
for i in range(N):
    tmp = A[i-1]
    if i != N-1:
        if A[i] != A[i+1]:
            now = A[i]
            for j in range(len(l)):
                if now % l[j] == 0:
                    flag = 0
                    break
                if now < l[j]*2:
                    flag = 1
                    break
            else:
                flag = 1
            if flag == 1:
                l.append(now)
                if i == 0 or now != tmp:
                    ans += 1
    else:
        now = A[i]
        for j in range(len(l)):
            if now % l[j] == 0:
                flag = 0
                break
            if now < l[j]*2:
                flag = 1
                break
        else:
            flag = 1
        if flag == 1:
            l.append(now)
            if i == 0 or now != tmp:
                ans += 1
print(ans)
#print(l)

### FIXED CODE ###

import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N = int(input())
A = list(map(int,(input().split())))
A.sort()
A.append(-1)
ans = 0
ok = [True]*(10**6+1)
for i in range(N):
    now = A[i]
    if now != A[i+1]:
        if ok[now]:
            if i == 0 or now != A[i-1]:
                ans += 1
            c = 1
            while now*c < 10**6+1:
                ok[now*c] = False
                c += 1
print(ans)
### BUGGY CODE ###

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

s = 0

for i in range(len(ai) - 1):
    for j in range(i + 1, len(ai)):
        s += (ai[i] * ai[j])
        s %= (10 ** 9 + 7)

print(s)

### FIXED CODE ###

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

square_sum_ai = sum(ai) ** 2
sum_ai_square = sum(map(lambda x: x ** 2, ai))

print(((square_sum_ai - sum_ai_square) // 2) % (10 ** 9 + 7))
### BUGGY CODE ###

class P:
    def __init__(self, c):
        self.c = c
        self.reached = False
        self.searched = False

from collections import deque
H, W = [int(i) for i in input().split()]
Ch, Cw = [int(i)-1 for i in input().split()]
Dh, Dw = [int(i)-1 for i in input().split()]
S = [[None for _ in range(H)] for _ in range(W)]
for y in range(H):
    tmp = input()
    for x in range(W):
        S[x][y] = P(tmp[x])

def neighbors(x, y, d):
    for i in range(max(0, x-1), min(W, x+2)):
        if S[i][y].reached == False and S[i][y].c == '.':
            d.append((i, y))
    for i in range(max(0, y-1), min(H, y+2)):
        if S[x][i].reached == False and S[x][i].c == '.':
            d.append((x, i))

def jump(x, y, d):
    for i in range(max(0, x-2), min(W, x+3)):
        for j in range(max(0, y-2), min(H, y+3)):
            if S[i][j].reached == False and S[i][j].searched == False and S[i][j].c == '.':
                d.append((i, j))
                S[i][j].searched = True


def BFS(x, y):
    if S[x][y].reached:
        return
    d = deque([(x, y)])
    while True:
        x, y = d.popleft()
        S[x][y].reached = True
        neighbors(x, y, d)
        if len(d) == 0:
            break


counter = 0
if Cw == Dw and Ch == Dh:
    print(0)
    exit()
q = deque([(Cw, Ch)])
flag = False
while True:
    while len(q) > 0:
        x, y = q.popleft()
        BFS(x, y)
    if S[Dw][Dh].reached == True:
        break
    counter += 1
    for i in range(W):
        for j in range(H):
            if S[i][j].reached:
                jump(i, j, q)
    if len(q) == 0:
        flag = True
        break
if flag:
    print(-1)
else:
    print(counter)
    


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections
import itertools
 
def main():
    input = sys.stdin.readline
    h, w = map(int, input().split())
    ch, cw = map(lambda x:int(x) - 1, input().split())
    dh, dw = map(lambda x:int(x) - 1, input().split())
    s = [list(input().rstrip()) for _ in range(h)]
    
    que = collections.deque()
    que.append((ch, cw))
    cost = [[float("INF")] * w for _ in range(h)]
    cost[ch][cw] = 0
    
    while que:
        py, px = que.popleft()
        for dy, dx in itertools.product(range(-2, 3), repeat = 2):
            ny, nx = py + dy, px + dx
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == ".":
                if dy == dx == 0:
                    continue
                if (dy, dx) in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                    if cost[ny][nx] > cost[py][px]:
                        cost[ny][nx] = cost[py][px]
                        que.appendleft((ny, nx))
                else:
                    if cost[ny][nx] > cost[py][px] + 1:
                        cost[ny][nx] = cost[py][px] + 1
                        que.append((ny, nx))
                        
    if cost[dh][dw] == float("INF"):
        print(-1)
    else:
        print(cost[dh][dw])
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
while True:
  for i in range(1,7):
    b = 2^(7-i)
    c = N%b
    if c ==0:
      break
    else:
      continue
    break
print(b)

### FIXED CODE ###

N = int(input())
while True:
    for i in range(7):
        b = 2**(6-i)
        if b <= N:
            break
    break
print(b)
### BUGGY CODE ###

import math

def  XYZTriplets():

    num = int(input())
    
    for i in range(1, num+1):
        count = 0

        x = 1
        y = 1
        z = 1

        for x in range(1, int(math.sqrt(num))):
            for y in range(1, int(math.sqrt(num))):
                for z in range(1, int(math.sqrt(num))):
            
                    function = 0.5*( (x+y)*(x+y) + (y+z)*(y+z) + (z+x)*(z+x) ) - i
                                
                    if function == 0:
                        count = count + 1
                        
                    
        print(count)
        

if __name__ == '__main__':
    XYZTriplets()


### FIXED CODE ###

import math
import numpy as np

def  XYZTriplets():

    num = int(input())
    
    list_num = []
    
    count = [0]*num
    
    for i in range(1, num+1):
        list_num.append(i)

    for x in range(1, int(math.sqrt(num))):
        for y in range(1, int(math.sqrt(num))):
            for z in range(1, int(math.sqrt(num))):
                
                function = x*x + y*y + z*z + x*y + y*z + z*x
                
                if function <= num and function > 0:
                    count[function-1] = count[function-1] + 1
 
    for i in range(0, num):
        print(count[i])
        

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

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    ans = 0
    for i in range(60):
        s = 0
        for a in A:
            if a & (1 << i):
                s += 1
        tmp = 0
        for j in range(N):
            if A[j] & (1 << i):
                s -= 1
                tmp += (N - j - 1) - s
            else:
                tmp += s
        ans = (ans + tmp * pow(2, i, MOD)) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())
    M = 61
    for i, a in enumerate(A):
        A[i] = list(map(int, str(format(a, 'b')).zfill(M)[::-1]))

    csum = [[0] * M for _ in range(N)]
    csum[0] = A[0]
    for i in range(1, N):
        for j in range(M):
            csum[i][j] = csum[i - 1][j] + A[i][j]

    p2 = [0] * M
    p2[0] = 1
    for i in range(M - 1):
        p2[i + 1] = p2[i] * 2 % MOD

    ans = 0
    for i, a in enumerate(A[1:], 1):
        for j in range(M):
            n = csum[i - 1][j] if a[j] == 0 else i - csum[i - 1][j]
            ans = (ans + n * p2[j]) % MOD

    print(ans)
    return


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

#-----combination計算部分------
def cmb(n, r):
    #if ( r<0 or r>n ):
    #    return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6*2
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#入力
r1,c1,r2,c2 = map(int, input().split())

sum = 0
for r in range(r1,r2+1):
    for c in range(c1,c2+1):
        sum += cmb(r+c,r)

print(sum % mod)

### FIXED CODE ###

#-----combination計算部分------
def cmb(n, r):
    #if ( r<0 or r>n ):
    #    return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6*2+2
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#入力
r1,c1,r2,c2 = map(int, input().split())

def g(r,c):
    gsum = 0
    for i in range(1,r+2):
        gsum += cmb(i+c,c)
    return gsum
'''
sum = 0
for r in range(r1,r2+1):
    for c in range(c1,c2+1):
        sum += cmb(r+c,r)
print(sum % mod)
'''
sum2 = g(r2,c2) - g(r1-1,c2) - g(r2,c1-1) + g(r1-1,c1-1)
print(sum2 % mod)
### BUGGY CODE ###

S=input()
Q=int(input())
for i in range(Q):
    A=list(input().split())
    if A[0]=="1":
        S=S[::-1]
    else:
        if A[1]=="1":
            S=A[2]+S
        else:
            S=S+A[2]
print(S)


### FIXED CODE ###

from collections import deque
S=deque(input())
Q=int(input())
rev=False
for i in range(Q):
    A=input().split()
    if A[0]=="1":
        if rev==False:rev=True
        else:rev=False
    else:
        if rev==False:
            if A[1]=="1":
                S.appendleft(A[2])
            else:
                S.append(A[2])
        else:
            if A[1]=="1":
                S.append(A[2])
            else:
                S.appendleft(A[2])
if rev:
    S.reverse()
print(*S,sep="")
### BUGGY CODE ###

N=int(input())
sum=1
mod=10**9+7
for i in range(1,N+1):
  sum*=i
print(sum%mod)

### FIXED CODE ###

N=int(input())
sum=1
mod=10**9+7
for i in range(1,N+1):
  sum*=i
  sum%=mod
print(sum)
### BUGGY CODE ###

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

mod = 10 ** 9 + 7
ans = sum((A[i] * A[j]) % mod for i in range(0,N-1) for j in range(i+1,N))

print(ans % mod)


### FIXED CODE ###

mod = 1000000007
N = int(input())
A = list(map(lambda x: int(x) % mod, input().split(" ")))

"""
累積話を計算しておく: O(N)
"""
_sum = 0
for i in range(N):
    _sum += A[i]
    _sum %= mod

"""
1重ループ内で下記を行う: O(N)

- 端のブロックを累積和から崩す（減算）
- 端のブロックと累積和をかける
- modをとる
"""
ans = 0
for i in range(N):
    # 累積和の端のブロックを崩す
    _sum -= A[i]

    ans += A[i] * _sum
    ans %= mod

print(ans)