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

# coding : utf-8

import math

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

print(max([i for i in range(1,int(M/N)+1) if M%i == 0]))

### FIXED CODE ###

from math import sqrt
 
n, m = map(int, input().split())
l = []
for i in range(1, int(sqrt(m)) + 1):
	if m % i == 0:
		l.append(i)
		l.append(m // i)
 
ans = 1
for d in l:
	if d * n <= m:
		ans = max(ans, d)
 
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import Counter, defaultdict


import sys
sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap



def f(c1, c2, c3):
    if min(c1, c2, c3) < 0:
        return 0
    if memo[c1][c2][c3] != -1:
        return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    p1 = c1 / N
    p2 = c2 / N
    p3 = c3 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    ret += f(c1-1, c2, c3) * p1 / ip0
    ret += f(c1+1, c2-1, c3) * p2 / ip0
    ret += f(c1, c2+1, c3-1) * p3 / ip0
    memo[c1][c2][c3] = ret
    return ret

N = read_int()
A = read_int_n()
memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
memo[0][0][0] = 0
ca = Counter(A)
print(f(ca[1], ca[2], ca[3]))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def f(c1, c2, c3):
    if memo[c1][c2][c3] != -1:
        return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    if c1 > 0:
        p1 = c1 / N
        ret += f(c1-1, c2, c3) * p1 / ip0
    if c2 > 0:
        p2 = c2 / N
        ret += f(c1+1, c2-1, c3) * p2 / ip0
    if c3 > 0:
        p3 = c3 / N
        ret += f(c1, c2+1, c3-1) * p3 / ip0
    memo[c1][c2][c3] = ret
    return ret


N = read_int()
A = read_int_n()
memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
memo[0][0][0] = 0
print(f(A.count(1), A.count(2), A.count(3)))
### BUGGY CODE ###

a,b,c,d,e,f = map(int, input().split())
con = list()
s = list()
for x in range(31):
    for y in range(31):
        for v in range(1501):
            if x == y == 0:
                continue
            else:
                w1 = (f-(100*a*x + 100*b*y + c*v))//d
                w2 = (100*a*x + 100*b*y -c*v)//d
                w3 = ((100*a*x + 100*b*y)*e -c*v*100)//(100*d)
                w = min(w1,w2,w3)
                con1 = 100*(c*v + d*w)/(100*a*x + 100*b*y +c*v +d*w)
                con.append(con1)
                s.append([x,y,v,w])
conm = max(con)
conin =con.index(conm)
t = s[conin]
# print(t)
ans1 = 100*a*t[0] + 100*b*t[1] + c*t[2] + d*t[3]
ans2 = c*t[2] + d*t[3]
print(ans1,ans2)


### FIXED CODE ###

a,b,c,d,e,f = map(int, input().split())
s = [0,0,0,0]
con1 = 0
for x in range(31):
    for y in range(31):
        for v in range(1501):
            if x == y == 0:
                continue
            else:
                w1 = (f-(100*a*x + 100*b*y + c*v))//d
                w2 = (100*a*x + 100*b*y -c*v)//d
                w3 = ((100*a*x + 100*b*y)*e -c*v*100)//(100*d)
                w = min(w1,w2,w3)
                con2 = 100*(c*v + d*w)/(100*a*x + 100*b*y +c*v +d*w)
                if con1 <= con2 and w >= 0:
                    con1 = con2
                    s = [x,y,v,w]
                else:
                    continue

ans1 = 100*a*s[0] + 100*b*s[1] + c*s[2] + d*s[3]
ans2 = c*s[2] + d*s[3]
print(ans1,ans2)
### BUGGY CODE ###

n, q = map(int, input().split())
s = str(input())
l = []
r = []

for i in range(q):
    l_e, r_e = map(int, input().split())
    l_e -= 1
    l.append(l_e)
    r.append(r_e)

for i in range(q):
    count = 0
    for j in range(l[i], r[i] - 1):
        if s[j] == "A" and s[j+1] == "C":
            count += 1
    print(count)



### FIXED CODE ###

n, q = map(int, input().split())
s = str(input())

count = [0] * n
for i in range(n - 1):
    if s[i:i+2] == "AC":
        count[i+1] = count[i] + 1
    else:
      count[i+1] = count[i]

for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    print(count[r] - count[l])
### BUGGY CODE ###

def main():  
  from collections import deque
  N = int(input())
  ab = [list(map(int,input().split())) for _ in range(N-1)]
  mod = 10**9+7
  fact = [1]*(N+1)
  fact_inv = [1]*(N+1)
  for i in range(1,N+1):
    fact[i] = (fact[i-1]*i)%mod
    fact_inv[i] = pow(fact[i], mod-2, mod)

  g = [deque([]) for _ in range(N+1)]
  for a,b in ab:
    g[a].append(b)
    g[b].append(a)

  parents = [0]*(N+1)
  q = deque([])
  s = deque([1])
  while s:
    x = s.pop()
    q.append(x)
    for y in g[x]:
      if y==parents[x]:
        continue
      else:
        parents[y] = x
        s.append(y)

  q = list(q)
  size_forward = [0]*(N+1)
  dp_forward = [1]*(N+1)
  for i in q[::-1]:
    p = parents[i]
    s = size_forward[i] + 1
    size_forward[p] += s
    dp_forward[i] *= fact[size_forward[i]]
    dp_forward[p] *= dp_forward[i] * fact_inv[s]
    dp_forward[p] %= mod

  size_back = [N-1-i for i in size_forward]
  dp_back = [1]*(N+1)
  for i in q[1:]:
    p = parents[i]
    x = dp_back[p]
    x *= fact_inv[size_back[p]]
    x *= dp_forward[p]
    x *= fact_inv[size_forward[p]]
    x *= fact[size_forward[i]+1]
    x *= pow(dp_forward[i],mod-2,mod)
    x *= fact[size_back[i]-1]
    dp_back[i] = x % mod

  for a,b,c,d in zip(size_forward[1:], dp_forward[1:], size_back[1:], dp_back[1:]):
    ans = b * d * fact[a+c] * fact_inv[a] * fact_inv[c]
    ans %= mod
    print(ans)
    
main()

### FIXED CODE ###

from collections import deque
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]
mod = 10**9+7
fact = [1]*(N+1)
fact_inv = [1]*(N+1)
for i in range(1,N+1):
  fact[i] = (fact[i-1]*i)%mod
  
fact_inv[-1] = pow(fact[-1], mod-2, mod)
for i in range(N,0,-1):
  fact_inv[i-1] = fact_inv[i] * i % mod

g = [deque([]) for _ in range(N+1)]
for a,b in ab:
  g[a].append(b)
  g[b].append(a)
  
parents = [0]*(N+1)
q = deque([])
s = deque([1])
while s:
  x = s.pop()
  q.append(x)
  for y in g[x]:
    if y==parents[x]:
      continue
    else:
      parents[y] = x
      s.append(y)
      
q = list(q)
size_forward = [0]*(N+1)
dp_forward = [1]*(N+1)
for i in q[::-1]:
  p = parents[i]
  s = size_forward[i] + 1
  size_forward[p] += s
  dp_forward[i] *= fact[size_forward[i]]
  dp_forward[p] *= dp_forward[i] * fact_inv[s]
  dp_forward[p] %= mod
  
size_back = [N-1-i for i in size_forward]
dp_back = [1]*(N+1)
for i in q[1:]:
  p = parents[i]
  x = dp_back[p]
  x *= fact_inv[size_back[p]]
  x *= dp_forward[p]
  x *= fact_inv[size_forward[p]]
  x *= fact[size_forward[i]+1]
  x *= pow(dp_forward[i],mod-2,mod)
  x *= fact[size_back[i]-1]
  dp_back[i] = x % mod
  
for a,b,c,d in zip(size_forward[1:], dp_forward[1:], size_back[1:], dp_back[1:]):
  ans = b * d * fact[a+c] * fact_inv[a] * fact_inv[c]
  ans %= mod
  print(ans)
### BUGGY CODE ###

# サンプル3
# 6
# 6 5 4 3 2 1
# b=3で2+0+2+4+6+8 = 22 b=4で1+1+3+5+7+9=26
# わからんからコード書いて試す
n = int(input())
a = list(map(int, input().split()))
# for b in range(-10, 10):
#     tmp = 0
#     for i, v in enumerate(a):
#         tmp += abs(v - (b + i + 1))
#     print(f"b={b}, tmp={tmp}")
# でかくても小さくてもダメっぽい
# 三分探索？やったことないしやり方わからんからググる
# めぐる式にこれhttps://qiita.com/ganariya/items/1553ff2bf8d6d7789127をしただけ

ok, ng = -10**9, 10**9 + 1


def calc(b):
    ret = 0
    for i, v in enumerate(a):
        ret += abs(v - (b + i + 1))
    return ret


# なぜかTLEなるのでカウンタを設置してみた
c = 0
while ng - ok > 1 or c < 100000:
    c += 1
    c1 = (2 * ok + ng) // 3
    c2 = (ok + 2 * ng) // 3
    b1, b2 = calc(c1), calc(c2)
    if b1 > b2:
        ok = c1 + 1  # +1のきもちは不明
    else:
        ng = c2

print(calc(ok))


### FIXED CODE ###

# サンプル3
# 6
# 6 5 4 3 2 1
# b=3で2+0+2+4+6+8 = 22 b=4で1+1+3+5+7+9=26
# わからんからコード書いて試す
n = int(input())
a = list(map(int, input().split()))
# for b in range(-10, 10):
#     tmp = 0
#     for i, v in enumerate(a):
#         tmp += abs(v - (b + i + 1))
#     print(f"b={b}, tmp={tmp}")
# でかくても小さくてもダメっぽい
# 三分探索？やったことないしやり方わからんからググる
# めぐる式にこれhttps://qiita.com/ganariya/items/1553ff2bf8d6d7789127をしただけ

ok, ng = -10**9, 10**9 + 1


def calc(b):
    ret = 0
    for i, v in enumerate(a):
        ret += abs(v - (b + i + 1))
    return ret


# なぜかTLEなるのでカウンタを設置してみた
c = 0
while c < 100:
    c += 1
    c1 = (2 * ok + ng) // 3
    c2 = (ok + 2 * ng) // 3
    b1, b2 = calc(c1), calc(c2)
    if b1 > b2:
        ok = c1 + 1  # +1のきもちは不明
    else:
        ng = c2

print(calc(ok))
### BUGGY CODE ###

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

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

MOD = 1000000007

def combinations(n, r):
    r = min(r, n - r)

    num = 1
    den = 1

    for i in range(1, r + 1):
        num = num * (n + 1 - i) % MOD
        den = den * i % MOD

    return num * pow(den, MOD - 2, MOD) % MOD


A.sort()

max_sum = 0
min_sum = 0
for i, a in enumerate(A):
    # max
    if i >= K - 1:
        max_sum += a * combinations(i, K - 1)

    # min
    if i <= N - K:
        min_sum += a * combinations(N - i - 1, K - 1)


print(int((max_sum - min_sum) % MOD))


### FIXED CODE ###

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

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

MOD = 1000000007


def combinations(n, r, MOD):
    if (r < 0) or (n < r):
        return 0

    r = min(r, n - r)
    return fact[n] * fact_inv[r] * fact_inv[n - r] % MOD


A.sort()
fact = [1, 1]
fact_inv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    fact_inv.append((fact_inv[-1] * inv[-1]) % MOD)

max_sum = 0
min_sum = 0

for i, a in enumerate(A):
    # max
    if i >= K - 1:
        max_sum += a * combinations(i, K - 1, MOD)

    # min
    if i <= N - K:
        min_sum += a * combinations(N - i - 1, K - 1, MOD)

print(int((max_sum - min_sum) % MOD))
### BUGGY CODE ###

import math

def floor(t):
    return math.floor(t)

def main():
    input1 = input().split()
    A = int(input1[0])
    B = int(input1[1])
    N = int(input1[2])

    output = 0
    result = 0
    for x in range(N+1):
        result = floor(A*x / B) - A*floor(x/B)
        if result > output:
            output = result

    print(output)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import math

input1 = input().split()
A = int(input1[0])
B = int(input1[1])
N = int(input1[2])

x = 0
result = 0
if N >= B-1:
    x = B-1
    result = (A*(x%B) - (A*x)%B)/B
elif N < B-1:
    x = N
    result = (A*(x%B) - (A*x)%B)/B

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

from bisect import bisect_left

N = int(input())
Lmat = [int(n) for n in input().split()]
Lmat.sort()

sum = 0
for i in range(N):
    for j in range(i+1,N):
        min_index = j
        max_index = bisect_left(Lmat, Lmat[i]+Lmat[j])
        sum+= bisect_left(Lmat, Lmat[i]+Lmat[j]) - j - 1
print(sum)


### FIXED CODE ###

import time
from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)

start = time.time()
res = 0
for i in range(n):
    for j in range(i+1,n):
        ab = l[i] + l[j]
        c_index = bisect_left(l, ab)
        res += c_index - j - 1
print(res)
### BUGGY CODE ###

S = str(input())
N = len(S)
cnt = 0

for i in range(N-3):
    for j in range(i+3,N+1):
        if int(S[i:j]) % 2019 == 0:
            cnt += 1

print(cnt)

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
g = [[] for i in range(n)]
l = [0] * (n-1)
for _ in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  l[_] = (min(a,b),max(a,b))
  g[a].append(b)
  g[b].append(a)
m = 0
for _ in range(n):
  if len(g[_]) > m:
    m = len(g[_])
    mi = _
print(m)
g2 = [set(range(1,m+1)) for i in range(n)]
deq = deque([mi])
vi = [0] * n
vi[mi] = 1
d = dict()
while deq:
  cur = deq.popleft()
  for i in g[cur]:
    if vi[i] == 1:
      continue
    else:
      vi[i] = 1
      deq.append(i)
      cu = (g2[cur]&g2[i]).pop()
      g2[cur].discard(cu)
      g2[i].discard(cu)
      d[(min(cur,i),max(cur,i))] = cu
for i in l:
  print(d[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
g = [[] for i in range(n)]
l = [0] * (n-1)
for _ in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  l[_] = (min(a,b),max(a,b))
  g[a].append(b)
  g[b].append(a)
m = 0
for _ in range(n):
  if len(g[_]) > m:
    m = len(g[_])
    mi = _
print(m)
g2 = [[] for i in range(n)]
stack = [(mi,-1)]
vi = [0] * n
vi[mi] = 1
d = dict()
while stack:
  pre,prei = stack.pop()
  c = 0
  for i in g[pre]:
    if vi[i] == 1:
      continue
    else:
      vi[i] = 1
      c += 1
      if c == prei:
        c += 1
      d[(min(pre,i),max(pre,i))] = c
      stack.append((i,c))
for i in l:
  print(d[i])
### BUGGY CODE ###

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
mod = 1_000_000_007
ans = 0
for i in range(n):
    for j in range(i+1,n):
        ans = (ans+a[i]*a[j]%mod)%mod
print(ans%mod)

### FIXED CODE ###

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
mod = 1_000_000_007
ans = 0
tmp = 0
for i in range(n-1,0,-1):
    tmp = (tmp+a[i])%mod
    ans += (tmp*a[i-1])%mod
print(ans%mod)
### BUGGY CODE ###

n,*h=map(int,open(0).read().split())
while len(h)>1:
    kh=set()
    for x in h:
        mn = min(h)
        md=x%mn
        if md!=0:
            kh.add(md)
        kh.add(mn)
    h=kh
print(mn)

### FIXED CODE ###

def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)

n,*h=map(int,open(0).read().split())

gh=gcd(h[0],h[1])
for i in range(2,n):
    gh=gcd(h[i],gh)

print(gh)
### BUGGY CODE ###

s = input()
t = input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

for i in range(1, len(s)+1):
    for j in range(1, len(t)+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i-1][j-1]+1, dp[i][j-1], dp[i-1][j])
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])
            
ans = ""
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if s[i-1] == t[j-1] and dp[i][j] == dp[i-1][j-1]+1:
        ans = s[i-1] + ans
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        i -= 1
        j -= 1
        
print(ans)

### FIXED CODE ###

s = input()
t = input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
            
i = len(s)
j = len(t)
ans = ""
while i > 0 and j > 0:
    if dp[i-1][j] == dp[i][j]:
        i -= 1
    elif dp[i][j-1] == dp[i][j]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1
        
print(ans)
### BUGGY CODE ###

k=int(input())
s=7
j=0
if(k%2==0):
  print("-1")
else:
    while(1):
        j=j+1
        if(s%k==0):
            break
        s=s*10+7
    print(j)
    

### FIXED CODE ###

k=int(input())
s=7
x=10000000
for i in range(x):
    if(s%k==0):
        print(i+1)
        break
    s=(s%k)*10+7
if(s%k!=0):
    print("-1")
### BUGGY CODE ###

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    import numpy as np
    A.sort()
    A = np.array(A)
    ans = sum(A)
    from bisect import bisect_left,bisect_right

    for i in range(q):
        b,c = map(int, input().split())
        start = bisect_left(A,b)
        end = bisect_right(A,b)
        A[start:end] = c
        A.sort()
        ans += (c-b)* (end-start)
        print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    import numpy as np
    A.sort()
    ans = sum(A)
    from bisect import bisect_left,bisect_right
    from collections import Counter
    count = Counter(A)
    for i in range(q):
        b,c = map(int, input().split())
        k = count[b]
        if k != 0:
            count[c] += count.pop(b)
        ans += (c-b)* k
        print(ans)


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

N = int(input())
num_lis = list(map(int, input().split()))
ans = 0
p = 10**9+7
for i in range(N-1):
  for j in range(i+1,N):
    ans += (num_lis[i]*num_lis[j])%p

print(ans%p)

### FIXED CODE ###

N = int(input())
num_lis = list(map(int, input().split()))
ans = 0
p = 10**9+7
s = sum(num_lis)
num = 0
for i in range(N):
  num += num_lis[i]
  ans += ((s-num)*num_lis[i])%p
  
print(ans%p)
### BUGGY CODE ###

import numpy as np
A, B = map(int, input().split())
while A%B > 0:
    c = A
    A = B
    B = c%B
P = [1]
if B%2 == 0:
    P.append(2)
for i in range(3, B//2 + 1, 2):
    if B%i == 0:
        P.append(i)
if B > 2:
    P.append(B)
    
l = len(P)
for i in range(2, l):
    if P[i] == 0:
        continue
    for j in range(i + 1, l):
        if P[j]%P[i] == 0:
            P[j] = 0
P = np.array(P)
print(np.where(P != 0)[0].size)

### FIXED CODE ###

def gcd(x, y):
    """
    ユークリッドの互除法を用いてxとyの最大公約数を求める。
    """
    while True:
        r = x%y
        if r == 0:
            break
        x = y
        y = r
    return y
    
def prime_factorize(x):
    """
    素因数分解
    """
    res = []
    while x%2 == 0:
        res.append(2)
        x = x//2
    p = 3
    while p*p <= x:
        while x%p == 0:
            res.append(p)
            x = x//p
        p += 2
    if x != 1:
        res.append(x)
    return res


A, B = map(int, input().split())
print(len(set(prime_factorize(gcd(A, B)))) + 1)
### BUGGY CODE ###

K,S = map(int, input().split())
print(sum([1 for k in range(0,K+1) for j in range(0,K+1) for i in range(0,K+1) if i+j+k == S]))

### FIXED CODE ###

K,S = map(int, input().split())
print(sum([1 for j in range(0,K+1) for i in range(0,K+1) if 0 <= S-i-j <= K ]))
### BUGGY CODE ###

S = input()
old_answer = [1 for i in range(len(S))]
new_answer = [0 for i in range(len(S))]
for _ in range(100000):
    new_answer = [0 for i in range(len(S))]
    for i in range(len(S)):
        if S[i] == "R":
            new_answer[i + 1] += old_answer[i]
        elif S[i] == "L":
            new_answer[i - 1] += old_answer[i]
    old_answer = new_answer
print(" ".join(map(str, new_answer)))

### FIXED CODE ###

S = input()

s_list = S.split("LR")
all_list = []

for idx, s in enumerate(s_list):
    if len(s_list) > 1:
        if idx != 0 and idx != len(s_list)-1:
            s = "R" + s + "L"
        elif idx == 0:
            s = s + "L"
        elif idx == len(s_list)-1:
            s = "R" + s
    s_len = len(s)
    R_count = s.count('R')
    L_count = s.count('L')
    R_list = [0 for _ in range(R_count)]
    L_list = [0 for _ in range(L_count)]

    if s_len % 2 == 0:
        R_list[R_count - 1] = s_len // 2
        L_list[0] = s_len // 2

    else:
        if R_count % 2 == 1:
            R_list[R_count - 1] = s_len - (s_len // 2)
            L_list[0] = s_len // 2
        else:
            R_list[R_count - 1] = s_len // 2
            L_list[0] = s_len - (s_len // 2)

    all_list.extend(R_list)
    all_list.extend(L_list)

print(" ".join(map(str, all_list)))
### BUGGY CODE ###

def main():
    from functools import reduce
    from fractions import gcd
    from collections import deque

    n, *a = map(int, open(0).read().split())
    p = deque(a)
    edge1 = reduce(gcd, a[1:])
    edge2 = reduce(gcd, a[:-1])
    full = reduce(gcd, a)
    ans = max([edge1, edge2, full])
    gl = p.pop()
    tmp = gl
    for i in range(n - 2):
        tmp2 = p.pop()
        gr = reduce(gcd, p)
        gl = gcd(gl, tmp)
        tmp = tmp2
        g = gcd(gl, gr)
        ans = max(ans, g)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from fractions import gcd

    n, *a = map(int, open(0).read().split())
    a = [0] + a + [0]
    l = [0 for _ in range(n + 1)]
    r = [0 for _ in range(n + 1)]
    tmpl = 0
    tmpr = 0
    for i in range(1,n+1):
        tmpl = gcd(tmpl, a[i-1])
        tmpr = gcd(tmpr, a[-i])
        l[i] = tmpl
        r[-i] = tmpr

    ans = 0
    for i, j in zip(l, r):
        g = gcd(i, j)
        ans = max(ans, g)

    print(ans)


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

import numpy as np

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

ans = []

for i in range(1, N+1):
    ans.append(A.index(i)+1)

print(*ans, sep=' ')


### FIXED CODE ###

import numpy as np

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

ans = [0] * N

for i in range(N):
    ans[A[i]-1] = i+1

print(*ans, sep=' ')
### BUGGY CODE ###

import math

def gcd(A,B,C):
    output = 1
    mini = min(A,B,C)
    for i in range(mini + 1,1,-1):
        if ((A%i == 0) and (B%i == 0) and (C%i == 0)):
            output = i
            break
    return output

K = int(input())
sum = 0
for A in range(1,K+1):
    for B in range(1,K+1):
        for C in range(1,K+1):
            if ((A == B) and (A == C)):
                sum = sum + A
            elif((B == C) and ( A != C)):
                sum = sum + (3 * gcd(A,B,C))
            elif(((A == B) and (A != C)) or ((A == C) and (A != B))):
                sum = sum + 0
            else:
                sum = sum + gcd(A,B,C)
print(sum)



### FIXED CODE ###

import math


temp = 0
K = int(input())
sum = 0
for A in range(1,K+1):
    for B in range(1,K+1):
        temp = math.gcd(A,B)
        for C in range(1,K+1):
            sum = sum + math.gcd(temp,C)
print(sum)
### BUGGY CODE ###

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

### FIXED CODE ###

a, b, n = map(int,input().split())
x = min(n,b-1)
print(int(a*(x%b) / b))
### BUGGY CODE ###

from itertools import combinations
N = int(input())
A = list(map(int, input().split()))
_sum = 0
k = 10**9+7
com = combinations(A,2)
for AA in com:
    _sum += (AA[0]*AA[1])%(k)
print(_sum%k)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 1000000007
S = 0
_sum = 0
for i in range(N):
    S += A[i]
    S %= mod
for i in range(N):
    S -= A[i]
    if S<0:
        S += mod
    _sum += A[i]*S
    _sum %= mod

print(_sum)