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

import fractions

N = int(input())
ints = list(map(int, input().split()))
# ints.sort(reverse=True)

gcd = 0
result = 1
holed_ints = []
for i in range(N):
    holed_ints = ints[:i] + ints[i+1:]
    gcd = 0
    for j in range(N-1):
        gcd = fractions.gcd(gcd, holed_ints[j])

    if gcd > result:
        result = gcd

print(result)

### FIXED CODE ###

import fractions

integral_count = int(input())
blackboard_integers = list(map(int, input().split()))

gcd_integers = list(set(blackboard_integers))

gcd = 0
result = 1
for i in range(len(gcd_integers)):
    gcd = 0
    if blackboard_integers.count(gcd_integers[i]) >= 2:
        for n in gcd_integers:
            gcd = fractions.gcd(gcd, n)
    else:
        for n in gcd_integers[:i]:
            gcd = fractions.gcd(gcd, n)
        for n in gcd_integers[i+1:]:
            gcd = fractions.gcd(gcd, n)
    if gcd > result:
        result = gcd

print(result)
### BUGGY CODE ###

n = int(input())
kehin = []
for i in range(n):
    s = input()
    if not s in kehin:
        kehin.append(s)
print(len(kehin))

### FIXED CODE ###

n = int(input())
kehin = []
for i in range(n):
    s = input()
    kehin.append(s)
kehin = set(kehin)
print(len(kehin))
### BUGGY CODE ###

def solve(maze,H, W, S, G):
    next_set = set()
    next_set.add(S)
    seen = [[False]*W for _ in range(H)]
    n = 0
    while True:
        curr_set = list(next_set)
        next_set = set()
        for x in curr_set:
            seen[x[0]][x[1]] == True
            if x == G:
                return n
            move_to = [(x[0]+1, x[1]), (x[0], x[1]+1), (x[0]-1, x[1]), (x[0], x[1]-1)] 
            for m in move_to:
                h, w = m
                if 0 <= h < H and 0<= w < W:
                    if maze[h][w] and seen[h][w] == False:
                        next_set.add(m)
        n += 1
    
    return print('error')

H, W = list(map(int, input().split()))
maze = [[True]*W for _ in range(H)]
for h in range(H):
    row = input()
    for w in range(W):
        if row[w] == '#':
            maze[h][w] = False

ans = 0
for i in range(H*W-1):
    for j in range(i+1, H*W):
        S = (i//W, i%W)
        G = (j//W, j%W)
        if maze[S[0]][S[1]] and maze[G[0]][G[1]]:
            ans = max(ans, solve(maze, H, W, S, G))

print(ans)

### FIXED CODE ###

def solve(maze,H, W, S):
    next_set = set()
    next_set.add(S)
    seen = [[False]*W for _ in range(H)]
    n = 0
    while next_set:
        n += 1
        curr_ = list(next_set)
        next_set = set()
        for h, w in curr_:
            if seen[h][w]:
                continue
            seen[h][w] = True
            for nh, nw in maze[h][w]:
                if seen[nh][nw] == False:
                    next_set.add((nh, nw))
    return n-1

# 入力
H, W = list(map(int, input().split()))
maze = [[[] for _ in range(W)] for _ in range(H)]
for h in range(H):
    row = input()
    for w in range(W):
        if row[w] == '#':
            maze[h][w] = False


# mazeに移動可能移動可能なマスを記録
for h in range(H):
    for w in range(W):
        if maze[h][w] == False:
            continue
        for nh, nw in [(h+1, w), (h, w+1), (h-1, w), (h, w-1)]:
            if 0 <= nh < H and 0<= nw < W:
                if maze[nh][nw] != False:
                    maze[h][w].append((nh, nw))
        # print(maze)
# print(maze)
ans = 0
for i in range(H*W-1):
        h = i//W
        w = i%W
        if maze[h][w]:
            ans = max(ans, solve(maze, H, W, (h, w)))

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

N = int(input())
A = [int(x) for x in input().split()]

while True:
    I = []
    count = 0
    for i in A:
        if i // 2 == 0:
            I.append(i)
            count += 1
        elif i//2 ==1:
            break

### FIXED CODE ###

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

c = 0

while all(i % 2 == 0 for i in A):
    A = [i/2 for i in A]
    c += 1
print(c)
### BUGGY CODE ###

n,k=(int(i) for i in input().split())
a=[int(i) for i in input().split()]
#print(n,k,a)

mylist=[]
for i in range(n):
  mylist.append(a.count(i))
mylist.sort(reverse=True)

val=0
for i in range(0,k):
  val+=mylist[i]
  
print(n-val)

### FIXED CODE ###

import collections

n,k=(int(i) for i in input().split())
a=[int(i) for i in input().split()]

mydata=collections.Counter(a)
mylist=list(mydata.values())
mylist.sort(reverse=True)
#print(mylist)

if len(mylist)<k:
  print(0)
else:
  val=sum(mylist[:k])
  print(n-val)
### BUGGY CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
l = factorization(n)
dic = []
for i in range(len(l)):
    tmp = l[i][0]
    dic.append(tmp)
    while n >= tmp:
        tmp *= l[i][0]
        if n < tmp:
            break
        dic.append(tmp)
dic.sort()
cnt = 0
while n != 1:
    flag = True
    for i in range(len(dic)):
        if n%dic[i] == 0:
            n //= dic[i]
            cnt += 1
            dic.pop(i)
            flag = False
            break
    if flag:
        break
print(cnt)

### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
if n == 1:
    print(0)
else:
    l = factorization(n)
    dic = []
    for i in range(len(l)):
        tmp = l[i][0]
        dic.append(tmp)
        while n >= tmp:
            tmp *= l[i][0]
            if n < tmp:
                break
            dic.append(tmp)
    dic.sort()
    cnt = 0
    while n != 1:
        flag = True
        for i in range(len(dic)):
            if n%dic[i] == 0:
                n //= dic[i]
                cnt += 1
                dic.pop(i)
                flag = False
                break
        if flag:
            break
    print(cnt)
### BUGGY CODE ###

from math import factorial

def power(a, b, p): #a^b (mod p)を求める #二分累乗法を使う
    if b == 0:
        return 1
    elif b % 2 == 0:
        x = power(a, b//2, p)
        return x ** 2 % p
    elif b % 2 == 1:
        y = power(a, b-1, p)
        return a * y % p

H, W, A, B = map(int, input().split())
C = H - A
D = W - B
p = 1000000007
b = power(factorial(B-1), p-2, p)
d = power(factorial(D-1), p-2, p)

x = 0
for i in range(C):
    k = factorial(i+B-1) % p
    l = factorial(D+H-i-2) % p
    x += (k * l * b * d * power(factorial(i), p-2, p) * power(factorial(H-i-1), p-2, p)) % p
print(x % p)


### FIXED CODE ###

H, W, A, B = map(int, input().split())
C = H - A
D = W - B
p = 1000000007

def power(a, b): #a^b (mod p)を求める #二分累乗法を使う
    if b == 0:
        return 1
    elif b % 2 == 0:
        return power(a, b//2) ** 2 % p
    else:
        return power(a, b//2) ** 2 * a % p

f = [1] #f[i] = i! % p
for i in range(H+W):
    f.append(f[i] * (i+1) % p)

I_f = [0] * (H+W+1) #I_f[i] = (i!)^(-1) % p
I_f[H+W] = power(f[H+W], p-2)
for i in reversed(range(H+W)):
    I_f[i] = I_f[i+1] * (i+1) % p

def combi(a, b): #(a+b)!/a!b! (mod p)を求める
    return f[a+b] * I_f[a] * I_f[b] % p

x = 0
for i in range(C):
    x = (x + combi(i, B-1) * combi(D-1, H-i-1)) % p
print(x)
### BUGGY CODE ###

n, m = map(int, input().split(' '))
s = [list(map(int, input().split(' '))) for _ in range(m)]
for i in range(m):
    s[i] = [s[i][0]-1,s[i][1]-1]
dic = [0]*n
count = 1
out_result = [int(n*(n-1)/2)]
for i in range(m-1,0,-1):
    if dic[s[i][1]] == 0 and dic[s[i][0]]==0:
        dic[s[i][0]] = count
        dic[s[i][1]] = count
        count += 1
        out_result.append(out_result[-1]-1)
    elif dic[s[i][0]]==0 and dic[s[i][1]]!=0:
        c = [x for x in dic if x == dic[s[i][1]]]
        out_result.append(out_result[-1]-len(c))
        dic[s[i][0]] = dic[s[i][1]]
    elif dic[s[i][0]]!=0 and dic[s[i][1]]==0:
        c = [x for x in dic if x == dic[s[i][0]]]
        out_result.append(out_result[-1]-len(c))
        dic[s[i][1]] = dic[s[i][0]]
    elif dic[s[i][0]] == dic[s[i][1]]:
        out_result.append(out_result[-1])
    else:
        c = [x for x in dic if x == dic[s[i][0]]]
        d = [x for x in dic if x == dic[s[i][1]]]
        out_result.append(out_result[-1]-len(c)*len(d))
        a = int(dic[s[i][1]])
        b = int(dic[s[i][0]])
        dic = [a if x==b  else x  for x in dic]
for i in range(1,m+1):
    print(out_result[-1*i])

### FIXED CODE ###

n, m = map(int, input().split(' '))
a = [0]*m
b = [0]*m
for i in range(m):
    a[i], b[i] = list(map(int, input().split(' ')))

c = [-1]*(m+2)

def find(num):
    if c[num] < 0:
        return num
    else:
        k = find(c[num])
        c[num] = k
        return k

result = [int(n*(n-1)/2)]
for i in range(m-1, 0,-1):
    x = find(a[i])
    y = find(b[i])

    if x != y:
        result.append(result[-1]-c[x]*c[y])
        x, y = sorted([x,y])
        c[x] += c[y]
        c[y] = x
    else:
        result.append(result[-1])

for i in result[::-1]:
    print(int(i))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Contents   : AtCoder Grand Contest 023
Author     : Kitaura Hiromi
LastUpdate : 20180428
Since      : 20180428
"""
N = int(input())
A = list(map(int, input().split(" ")))


# O(N^2)
cnt = 0
for i in range(N):
    for j in range(i+1, N+1):
        if sum(A[i:j]) == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Contents   : AtCoder Grand Contest 023
Author     : Kitaura Hiromi
LastUpdate : 20180502
Since      : 20180428
"""
N = int(input())
A = list(map(int, input().split(" ")))

# O(NlogN)
S = []
tmp = 0
for i in range(N):
    S.append(tmp)
    tmp += A[i]
S.append(tmp)
S = sorted(S)
cnt = 1
ret = 0
tmp = S[0]
for i in range(1, len(S)):
    if tmp == S[i]:
        cnt += 1
    else:
        ret += cnt * (cnt - 1) // 2
        cnt = 1
        tmp = S[i]
ret += cnt * (cnt - 1) // 2
print(ret)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

mod = 10**9+7

dp = [0] * (n+1)
dp[0] = 1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2, n+1):
    if i not in a:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] = dp[i]%mod
    else:
        dp[i] = 0

#print(dp)
print(dp[-1])


### FIXED CODE ###

# -*- coding: utf-8 -*-

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

stairs = [i for i in range(1, n+1)]
a = [0 for _ in range(m)]
for i in range(m):
  a[i] = int(input())
a = set(a)
  
mod = 10**9+7
dp = [0] * (n+1)
dp[0] = 1

#print(test_a)
for i in range(1, n+1):
    if i in a:
        continue
    dp[i] = dp[i] + dp[i-1]
    if i > 1:
        dp[i] = dp[i] + dp[i-2]

#print(dp)
print(dp[-1]%mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
k, q = map(int, input().split())
d = list(map(int, input().split()))

query = []
for _ in range(q):
    query.append(tuple(map(int, input().split())))

for n, x, m in query:
    l = []
    for i in range(k):
        l.append(d[i]%m)
    zero = l.count(0)
    total = x%m
    total += sum(l)*((n-1)//k)
    zero_total = zero*((n-1)//k)

    s = n
    n -= 1
    n -= n//k * k
    t = 0
    for i in range(n):
        t += l[i]

    total += t

    zero_total += l[:n].count(0)
    print(s-1-total//m-zero_total)


### FIXED CODE ###

import sys
input = sys.stdin.readline
k, q = map(int, input().split())
d = list(map(int, input().split()))
query = [None]*q
for i in range(q):
    query[i] = list(map(int, input().split()))

def answer_query(n, x, m):
    l = [m if i%m == 0 else i%m for i in d]
    count = n // k
    rem = n % k
    s = sum(l)
    total = s%m * count + x%m
    for i in range(rem):
        total += l[i]

    total //= m
    total += s//m * count

    print(n-total)


for n, x, m in query:
    answer_query(n-1, x, m)
### BUGGY CODE ###

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

ans = 0
for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        for k in range(j+1, N):
            c = L[k]
            if a < b+c and b < a+c and c < a+b:
                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):
    for j in range(i+1, N):
        index = bisect.bisect_left(L, L[i]+L[j])
        ans += index - 1 - j
print(ans)
### BUGGY CODE ###

n = int(input())
s = list(input())
s = [int(s[i]) for i in range(n)]

cnt = 0
for i in range(1000):
    c = [int(i/100), int((i/10)%10), int(i%10)]
    f = 0
    for j in range(n):
        if s[j] == c[f]:
            f += 1
        if f == 3:
            break
    if f == 3:
        cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
S = list(input())
PIN = []
b1 = []
for i in range(N-2):
    b2 = []
    if S[i] in b1:
        continue
    else:
        b1.append(S[i])
    for j in range(i+1, N-1):
        b3 = []
        if S[j] in b2:
            continue
        else:
            b2.append(S[j])
        for k in range(j+1, N):
            if S[k] in b3:
                continue
            else:
                b3.append(S[k])
            cand = S[i] + S[j] + S[k]
            PIN.append(cand)

print(len(set(PIN)))
### BUGGY CODE ###

B, W = list(map(int, input().split()))

MOD = 10**9+7
facts = [1,1]
invs = [1,1]
invfacts = [1,1]
for ind in range(1, B+W):
    i = ind+1
    facts += [ facts[-1]*i % MOD ]
    invs += [ -(MOD//i)*invs[MOD%i] % MOD ]
    invfacts += [ invfacts[-1]*invs[i] % MOD ]

y_pi = 0 #i回目までにBを食べ尽くした確率piの分子
y_qi = 0 #i回目までにWを食べ尽くした確率qiの分子
pow2 = 1
inv2i = 1
for i in range(B+W):
    y_pi = 0 if i < B else 2*y_pi + ((facts[i-1]*invfacts[i-B] % MOD)*invfacts[B-1] % MOD)
    y_qi = 0 if i < W else 2*y_qi + ((facts[i-1]*invfacts[i-W] % MOD)*invfacts[W-1] % MOD)
    invxi = inv2i * invs[2] % MOD
    yi = (pow2-y_pi+y_qi) % MOD
    z = yi*invxi % MOD
    print(z)
    pow2 = pow2*2 %MOD
    inv2i = invxi

### FIXED CODE ###

B, W = list(map(int, input().split()))

MOD = 10**9+7

facts = [1,1] #階乗
invs = [1,1] #整数の逆元
invfacts = [1,1] #階乗の逆元
for ind in range(1, B+W):
    i = ind+1
    facts.append(facts[-1]*i % MOD)
    invs.append( -(MOD//i)*invs[MOD%i] % MOD )
    invfacts.append( invfacts[-1]*invs[i] % MOD )

def Comb(n, r, MOD=MOD):
    if n < r:
        return 0
    return facts[n]*invfacts[n-r]*invfacts[r] % MOD

y_pi = 0 #i回目までにBを食べ尽くした確率piの分子
y_qi = 0 #i回目までにWを食べ尽くした確率qiの分子
pow2 = 1
invxi = 1
inv2 = invs[2]
for i in range(B+W):
    #y_pi = 0 if i < B else 2*y_pi + ((facts[i-1]*invfacts[i-B] % MOD)*invfacts[B-1] % MOD)
    y_pi = (2*y_pi + Comb(i-1, B-1))%MOD
    #y_qi = 0 if i < W else 2*y_qi + ((facts[i-1]*invfacts[i-W] % MOD)*invfacts[W-1] % MOD)
    y_qi = (2*y_qi + Comb(i-1, W-1))%MOD
    invxi = invxi * inv2 % MOD
    yi = (pow2-y_pi+y_qi) % MOD
    z = yi*invxi % MOD
    print(z)
    pow2 = pow2*2 %MOD
### BUGGY CODE ###

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


### FIXED CODE ###

S = input()
Q = int(input())
bs = ''
fs = ''
hanten = 0
for i in range(Q):
    query = list(input().split())
    if query[0] == '1':
        hanten += 1
    else:
        if query[1] == '1':
            if hanten % 2 == 0:
                fs += query[2]
            else:
                bs += query[2]
        else:
            if hanten % 2 == 0:
                bs += query[2]
            else:
                fs += query[2]
if hanten % 2 == 0:
    print(fs[::-1]+S+bs)
else:
    print(bs[::-1]+S[::-1]+fs)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('Inf')] * (10 ** 5 + 1)
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i + j < n:
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[n - 1])

### FIXED CODE ###

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

dp = [float('Inf') for _ in range(n)]
dp[0] = 0
for i in range(1, n):
    for j in range(1, k + 1):
        if i - j >= 0:
            if dp[i] > dp[i - j] + abs(a[i] - a[i - j]):
                dp[i] = dp[i - j] + abs(a[i] - a[i - j])
print(dp[n - 1])
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
for i in range(1,n):
    print(l.count(i))
print(0)


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
m=[0]*n
for i in l:
    m[i-1]+=1
for j in range(n):
    print(m[j])
### BUGGY CODE ###

import itertools


def main():
    N = int(input())
    S = input()

    str_list = list()
    for s in S:
        str_list.append(s)

    str_uni_list = {}
    for str in str_list:
        if (str in str_uni_list) is False:
            str_uni_list[str] = 1
        else:
            str_uni_list[str] += 1

    list_val = []
    for i in str_uni_list.values():
        list_val.append(i)

    ans = 0
    temp = 1
    for i in range(1, len(list_val) + 1):
        for j in list(itertools.combinations(list_val, i)):
            for k in j:
                temp *= k
            ans += temp
            temp = 1

    print(ans % (10 ** 9 + 7))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()

    str_list = list()
    for s in S:
        str_list.append(s)

    str_uni_list = {}
    for str in str_list:
        if (str in str_uni_list) is False:
            str_uni_list[str] = 1
        else:
            str_uni_list[str] += 1

    list_val = []
    for i in str_uni_list.values():
        list_val.append(i)

    rem = 1
    for v in list_val:
        rem *= (v + 1)

    ans = rem - 1

    print(ans % (10 ** 9 + 7))


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

import numpy as np

N, W = map(int, input().split())
wv = []
for i in range(N):
    w, v = map(int, input().split())
    wv.append([w,v])

#i番目までを使ってjの重さで入れたときの価値の最大値を記録する
dp = np.zeros((N+1,W+1))
for j in range(1,W+1):
    for i in range(1,N+1):
        if j < wv[i-1][0]:
            dp[i,j] = dp[i-1,j]
        else:
            dp[i,j] = max(dp[i-1,j-wv[i-1][0]] + wv[i-1][1], dp[i-1,j])
print(int(dp[-1][-1]))

### FIXED CODE ###

import numpy as np

N, W = map(int, input().split())
wv = []
#i番目までを詰めたときの最大の価値を記録
dp = np.zeros(W+1)
for i in range(N):
    w, v = map(int, input().split())
    dp[w:] = np.maximum(dp[:-w]+v, dp[w:])

print(int(dp[-1]))
### BUGGY CODE ###

a,b=map(int,input().split())
print([_+y+z for _ in range(a+1) for y in range(a+1) for z in range(a+1)].count(b))



### FIXED CODE ###

k,s=map(int,input().split())
print(len([1 for z in range(k+1) for y in range(k+1) if 0<=s-y-z<=k]))
### BUGGY CODE ###

MOD = 10**9 + 7
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (1 << N)
dp[0] = 1
prev = [0]
for i in range(N):
    temp = []
    for j in range(N):
        if A[i][j] != 1: continue
        bit = 1 << j
        for s in prev:
            if s & bit == 0:
                new_s = s | bit
                dp[new_s] += dp[s]
                dp[new_s] %= MOD
                temp.append(new_s)
    prev = list(set(temp))
print(dp[(1 << N) - 1])

### FIXED CODE ###

MOD = 10**9 + 7
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (1 << N)
dp[0] = 1
bits = [1 << i for i in range(N)]
cands = [[] for _ in range(N+1)]
for s in range(1 << N):
    temp = 0
    for n in range(N):
        if s & (1 << n): temp += 1
    cands[temp].append(s)
for i, a in enumerate(A):
    for j in [k for k, v in enumerate(a) if v == 1]:
        bit = bits[j]
        for s in cands[i]:
            if s & bit == 0:
                new_s = s | bit
                dp[new_s] += dp[s]
                dp[new_s] %= MOD
print(dp[-1])
### BUGGY CODE ###

#ALDS1_4-D Allocation
from collections import deque

def pIsAccptbl(w,k,p):
    tr = 0
    c = 0
    while(w):
        tmp = w.popleft()
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp

    c+=1
    if c>k:
        return False
    else:
        return True
    
n,k = input().split()
w = []
for i in range(int(n)):
    w.append(int(input()))

p = max(w)

while(1):
    x=deque(w)
    if(pIsAccptbl(x,int(k),p)):
        print(p)
        break
    else:
        p+=1

### FIXED CODE ###

from collections import deque

def isPa(w,k,p):
    tr = 0
    c = 0
    d = deque(w)
    while(d):
        tmp = d.popleft()
        if(tmp > p):
            return False
        
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:
            return False
    return True

def MaxInP(w,k,p):
    maxinp = 0
    tmp = 0
    d = deque(w)
    while(d):
        tmp += d.popleft();
        if(tmp > p):
            if(tmp > maxinp):
                maxinp = tmp
            tmp = 0
    return maxinp

n,k = [int(x) for x in input().split()]
w = deque()
for i in range(n):
    w.append(int(input()))
    
mean = int(sum(w)/k)
maxinp = MaxInP(w,k,mean)

if k == 1:
    print(mean)
else:
    minP = mean
    maxP = maxinp
    while(True):
        m = int ((minP + maxP)/2)
        if ( isPa(w,k,m) ):
            maxP = m
        else:
            minP = m
        if (minP+1 == maxP or minP == maxP):
            print(maxP)
            break
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import bellman_ford


def solve(N,L,edges,queries):

    graph = np.zeros((N,N),dtype=int)
    for a,b,c in edges:
        graph[a-1,b-1] = c
        graph[b-1,a-1] = c

    dist = bellman_ford(graph, directed=False)
    dist[dist<=L] = 1
    dist[dist>L] = 0

    dist = bellman_ford(dist, directed=False)
    res = []
    for a,b in queries:
        d = dist[a-1,b-1]
        res.append(int(d-1) if d != float('inf') else -1)
    return res

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

if __name__ == '__main__':

    t = read().split()

    N,M,L = map(int,t[:3])

    m = map(int,t[3:M*3+3])
    edges = zip(m,m,m)

    Q = int(t[M*3+3])
    m = map(int, t[M*3+4:])
    queries = zip(m,m)

    print(*solve(N,L,edges,queries), sep='\n')

### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import floyd_warshall


def solve(N,L,edges,queries):

    graph = np.zeros((N,N),dtype=int)
    for a,b,c in edges:
        graph[a-1,b-1] = c
        graph[b-1,a-1] = c

    dist = floyd_warshall(graph, directed=False)
    dist = (dist<=L)
    dist = floyd_warshall(dist, directed=False)
    res = []
    for a,b in queries:
        d = dist[a-1,b-1]
        res.append(int(d-1) if d != float('inf') else -1)
    return res

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

if __name__ == '__main__':

    t = read().split()

    N,M,L = map(int,t[:3])

    m = map(int,t[3:M*3+3])
    edges = zip(m,m,m)

    Q = int(t[M*3+3])
    m = map(int, t[M*3+4:])
    queries = zip(m,m)

    print(*solve(N,L,edges,queries), sep='\n')
### BUGGY CODE ###

M=1000000007
s=0
n=int(input())
a=list(map(int,input().split()))
for i in range(n-1):
    for j in range(i+1,n):
        s+=(a[i]%M*a[j]%M)%M
print(s%M)
        
    

### FIXED CODE ###

M=1000000007
def findProductSum(A, n): 
    s = 0
    for i in range(n): 
        s+=A[i] 
    array_sum_square = s*s
    individual_square_sum = 0
    for i in range(n): 
        individual_square_sum += A[i]*A[i]
    return (array_sum_square -individual_square_sum) // 2
n=int(input())
a=list(map(int,input().split()))
print(findProductSum(a,n)%M)