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

n,c = map(int,input().split())
d = [0]
for i in range(c):
    d.append([0] + list(map(int,input().split())))
li0 = []
li1 = []
li2 = []
for i in range(n):
    g = list(map(int,input().split()))
    for j in range(n):
        if (i + j) % 3 == 0:
            li0.append(g[j])
        if (i + j) % 3 == 1:
            li1.append(g[j])
        if (i + j) % 3 == 2:
            li2.append(g[j])
ans = 100000000
for i in range(1,c+1):
    for j in range(1,c+1):
        for k in range(1,c+1):
            if i == j or j == k or i == k:
                continue
            x = 0
            for color in li0:
                x += d[color][i]
            for color in li1:
                x += d[color][j]
            for color in li2:
                x += d[color][k]
            ans = min(x,ans)
print(ans) 


### FIXED CODE ###

from collections import defaultdict
n,c = map(int,input().split())
d = [0]
for i in range(c):
    d.append([0] + list(map(int,input().split())))
li0 = []
li1 = []
li2 = []
for i in range(n):
    g = list(map(int,input().split()))
    for j in range(n):
        if (i + j) % 3 == 0:
            li0.append(g[j])
        if (i + j) % 3 == 1:
            li1.append(g[j])
        if (i + j) % 3 == 2:
            li2.append(g[j])
dic0 = defaultdict(int)
dic1 = defaultdict(int)
dic2 = defaultdict(int)
for i in li0:
    dic0[i] += 1
for i in li1:
    dic1[i] += 1
for i in li2:
    dic2[i] += 1 
ans = 1000000000
for i in range(1,c+1):
    for j in range(1,c+1):
        for k in range(1,c+1):
            if i == j or j == k or i == k:
                continue
            x = 0
            for color in range(1,c+1):
                x += dic0[color] * d[color][i]
                x += dic1[color] * d[color][j]
                x += dic2[color] * d[color][k]
            ans = min(x,ans) 
print(ans)
### BUGGY CODE ###

import math
a,b=map(int,input().split())
a,b=min(a,b),max(a,b)
ans=1
for i in range(2,a+1):
  if a%i==0:
    if b%i==0:
      ans+=1
    while a%i==0:
      a//=i
    if a==1:
      break
print(ans)

### FIXED CODE ###

from fractions import gcd
import math
a,b=map(int,input().split())
g=gcd(a,b)
ans=1
for i in range(2,math.floor(g**.5)+1):
  if g%i==0:
    ans+=1
    while g%i==0:
      g//=i
if g!=1:
  ans+=1
print(ans)
### BUGGY CODE ###

def solve():
    N, K = map(int, input().split())
    
    ans = 0
    while N > 0:
        N // K
        ans += 1
    
    print(ans)
    
if __name__ == '__main__':
    solve()

### FIXED CODE ###

def solve():
    N, K = map(int, input().split())
    
    ex = 1
    while K ** ex <= N:
        ex += 1
    print(ex)
    
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

import sys
import collections
input = sys.stdin.readline

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

N  = int(input())
lst_A = list(map(int, input().split()))
mod = 10**9+7


lcm_lst = {}
lst_c = []
for i in lst_A:
	c = collections.Counter(prime_factorize(i))
	lst_c.append(c)
	for key in c:
		if key in lcm_lst:
			if(lcm_lst[key]<c[key]):
				lcm_lst[key]=c[key]
		else:
			lcm_lst[key]=c[key]

ans = 0
for c in lst_c:
	a = 1
	for key in lcm_lst:
		if key in c:
			a = (a * key **(lcm_lst[key] - c[key]))%mod
		else:
			a = (a * key **(lcm_lst[key]))%mod
	ans =  (ans + a )% mod
print(ans)

### FIXED CODE ###

import sys,fractions
input = sys.stdin.readline

mod = 10**9+7

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

lcm = 1
for a in lst_a:
    lcm = a*lcm//fractions.gcd(a,lcm)
lcm %= mod
ans = 0
for a in lst_a:
	ans += lcm*pow(a,mod-2,mod)
	ans %= mod

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

from collections import deque
H, W = map(int, input().split())

route = []
for _ in range(H):
  route.append(input())
  
dp = [[0 for _ in range(W)] for __ in range(H)]

wall = set()
start_list = []
for y, r in enumerate(route):
  for x, w in enumerate(r):
    if w == '#':
      wall.add((x, H-y-1))
    else:
      start_list.append((x, H-y-1))

score = -1
for xy in start_list:
  d = deque()
  d.append((xy[0],xy[1],0))
  step = 0
  already = set() | wall
  while len(d) > 0:
    now = d.popleft()
    already.add(now[:-1])
    step = now[2]+1
    x,y = now[0]-1, now[1]
    if (x, y) not in already and x >= 0:
      d.append((x, y, step))
    x, y = x+1, y-1
    if (x, y) not in already and y >= 0:
      d.append((x, y, step))
    x, y = x+1, y+1
    if (x, y) not in already and x < W:
      d.append((x, y, step))
    x, y = x-1, y+1
    if (x, y) not in already and y < H:
      d.append((x, y, step))
  score = max(step-1, score)
  
print(score)

### FIXED CODE ###

from collections import deque
import copy
H, W = map(int, input().split())
 
route = []
for _ in range(H):
  route.append(input())
  
wall = set()
start = set()
for y, r in enumerate(route):
  for x, w in enumerate(r):
    if w == '.':
      start.add((x, y))

score = -1
ssize = [(-1,0),(0,-1),(1,0),(0,1)]
for xy in start:
  d = deque()
  d.append((xy+(0,)))
  step = 0
  can = copy.deepcopy(start)
  can.remove(xy)
  while len(d) > 0:
    now = d.popleft()
    step = now[2]
    for xs, ys in ssize:
      nxt = (now[0]+xs, now[1]+ys)
      if nxt in can:
        d.append(nxt+(step+1,))
        can.remove(nxt)
  score = max(step, score)
  
print(score)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
min = min(A)
max = max(A)
sum = 0
for i in range(min,max + 1):
    j = A.count(i)
    sum += j * (j - 1) // 2
for i in A:
    print(sum - A.count(i) + 1)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
c= Counter(A)
sum = 0
for i in c.values():
    sum += i * (i - 1) // 2
for i in A:
    print(sum - c[i] + 1)
### BUGGY CODE ###

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

import functools
import operator
prod = functools.partial(functools.reduce, operator.mul)

# print(A)

# i=K+1の時、直近K回の期末テストの点数
p_K = prod(A[:K])
# print(p_K)
for i in range(K, N):
    # print(i)
    p_Kp1 = p_K / A[i-K] * A[i]
    # print(p_Kp1)
    if p_K < p_Kp1:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

# import functools
# import operator
# prod = functools.partial(functools.reduce, operator.mul)

# i=K+1の時、直近K回の期末テストの点数
# p_K = prod(A[:K])
p_K = 1

for i in range(K, N):
    t = A[i] / A[i-K]
    p_Kp1 = p_K * t
    if p_K < p_Kp1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
maxr = N // R
maxg = N // G
count = 0
for i in range(maxr+1):
    for j in range(maxg+1):
        nokori = N - i * R - j * G
        amari = nokori % B
        if nokori >= 0 and amari == 0:
            count += 1
print(count)


### FIXED CODE ###

R, G, B, N = map(int, input().split())
color = [R, G, B]
color.sort(reverse = True)
maxr = N // color[0]
count = 0
for i in range(maxr+1):
    nokori = N - i * color[0]
    maxg = nokori // color[1]
    for j in range(maxg+1):
        nokorinow = nokori - j * color[1]
        amari = nokorinow % color[2]
        if amari == 0:
            count += 1

print(count)
### BUGGY CODE ###

n,m,*L=map(int,open(0).read().split())
con=[[] for _ in range(n)]
c=[True]*n
for s,t in zip(*[iter(L)]*2):
	con[s-1]+=[t-1]
	c[t-1]=False
for i in range(n):
	if c[i]:
		root=i
		break
q=[root]
ans=[0]*n
while q:
	cur=q.pop(0)
	for nxt in con[cur]:
		ans[nxt]=cur+1
		q.append(nxt)
print("\n".join(map(str,ans)))

### FIXED CODE ###

def topologicalSort(g: list, deg: list):
	ret = []
	q = []
	for i, d in enumerate(deg):
		if not d:
			ret.append(i)
			q.append(i)
	while q:
		cur = q.pop(0)
		for nxt in g[cur]:
			deg[nxt] -= 1
			if not deg[nxt]:
				ret.append(nxt)
				q.append(nxt)
	return ret

def main():
	v, e, *L = map(int, open(0).read().split())
	g = [[] for _ in range(v)]
	rev = [[] for _ in range(v)]
	deg = [0] * v
	for s, t in zip(*[iter(L)] * 2):
		g[s - 1].append(t - 1)
		rev[t - 1].append(s - 1)
		deg[t - 1] += 1
	order = topologicalSort(g, deg)
	idx = [None] * v
	for i, o in enumerate(order):
		idx[o] = i
	ans = [0] * v
	for i in range(v):
		if rev[i]:
			ans[i] = max(rev[i], key=lambda x: idx[x]) + 1
	print("\n".join(map(str, ans)))

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

from collections import deque
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
n = h*w


def to_v(i, j):
    return i*w+j


INF = 10**18
dist = [INF]*n
init_vs = []
for i in range(h):
    for j, x in enumerate(input()):
        if x == '#':
            v = to_v(i, j)
            init_vs.append(v)
            dist[v] = 0


def generate_v2(v):
    i, j = divmod(v, w)
    if 0 < i:
        yield v-w
    if i < h-1:
        yield v+w
    if 0 < j:
        yield v-1
    if j < w-1:
        yield v+1


def bfs(init_vs):
    next_v = deque([*init_vs])
    while next_v:
        v = next_v.popleft()
        for v2 in generate_v2(v):
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)


bfs(init_vs)
print(max(dist))


### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
n = h*w


def to_v(i, j):
    return i*w+j


init_vs = []
for i in range(h):
    for j, x in enumerate(input()):
        if x == '#':
            init_vs.append(to_v(i, j))


INF = 10**18
dist = [INF]*n
for v in init_vs:
    dist[v] = 0


def generate_v2(v):
    i, j = divmod(v, w)
    if 0 < i:
        yield v-w
    if i < h-1:
        yield v+w
    if 0 < j:
        yield v-1
    if j < w-1:
        yield v+1


def bfs(init_vs):
    next_v = deque([*init_vs])
    while next_v:
        v = next_v.popleft()
        for v2 in generate_v2(v):
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)


bfs(init_vs)
print(max(dist))
### BUGGY CODE ###

import itertools
import fileinput


def solve_match(match_matrix):
    size = len(match_matrix)
    combo_dict = {}

    r = tuple(range(size))

    for col in range(size):
        for combo in itertools.combinations(r, col + 1):
            if col == 0:
                combo_dict[combo] = match_matrix[combo[0]][col]
            else:
                s = 0
                for i, row_num in enumerate(combo):
                    if match_matrix[row_num][col] == 1:
                        s += combo_dict[combo[:i] + combo[i + 1:]]
                combo_dict[combo] = s
    return combo_dict[r]


inp = fileinput.FileInput()
n = int(inp.readline())

arr = []
for _ in range(n):
    arr.append([int(v) for v in inp.readline().split(" ")])

print(solve_match(arr))


### FIXED CODE ###

import itertools
import fileinput
 
 
def solve_match(match_matrix):
    size = len(match_matrix)

    combo_list = [0] * (2**size)

    combo_indexes = [[] for _ in range(size + 1)]
    for i in range(2**size):
        count = 0
        n = i
        while (n): 
            count += n & 1
            n >>= 1
        combo_indexes[count].append(i)

    for col in range(size):
        for combo in combo_indexes[col + 1]:
            if col == 0:
                for i in range(size):
                    if (combo & (1 << i)):
                        combo_list[combo] = match_matrix[i][col]
                        break
            else:
                s = 0
                cnt = 0
                for i in range(size):
                    flag = 1 << i
                    if (combo & flag) and match_matrix[i][col] == 1:
                        s += combo_list[combo & (~flag)]
                        cnt += 1
                        if cnt == col + 1:
                            break
                
                combo_list[combo] = s % (10**9 + 7)
    return combo_list[-1]
 
 
inp = fileinput.FileInput()
n = int(inp.readline())
 
arr = []
for _ in range(n):
    arr.append([int(v) for v in inp.readline().split(" ")])
 
print(solve_match(arr))
### BUGGY CODE ###

n = int(input())
s = str(input())
r = []
g = []
b = []
for i in range(n):
    if s[i] == "R":
        r.append(i+1)
    elif s[i] == "G":
        g.append(i+1)
    else:
        b.append(i+1)
cnt = 0
for i in r:
    for j in g:
        if (i+j)%2==0:
            if (i + j) // 2 in b:
                cnt += 1
        if (2 * j) - i in b:
            cnt += 1
        if (2 * i) - j in b:
            cnt += 1
print((len(r) * len(g) * len(b))-cnt)


### FIXED CODE ###

n = int(input())
s = str(input())
r = []
g = []
b = []
for i in range(n):
    if s[i] == "R":
        r.append(i+1)
    elif s[i] == "G":
        g.append(i+1)
    else:
        b.append(i+1)
cnt=len(r)*len(g)*len(b)
if n<=3:
    print(0)
    exit()
for i in range(n-2):
    for j in range(i+1,n-1):
        if j*2-i<n:
            if s[i]!=s[j] and s[j]!=s[j*2-i] and s[j*2-i]!=s[i]:
                cnt-=1
print(cnt)
### BUGGY CODE ###

H, W, K = map(int, input().split())
items = []

start = []
diff = float("inf")
p = []
prev = [[False] * W for _ in range(H)]
for i in range(H):
    items.append(list(input()))
    for j in range(W):
        s = items[i][j]
        if s == "S":
            start = [i, j]
            diff = min(diff, min(i, H - 1 - i, min(j, W - 1 - j)))
            p = [i, j]
            prev[i][j] = True

from collections import deque

que = deque([])

dx = [-1, 0, 0, 1]
dy = [0, 1, -1, 0]

for i in range(4):
    x = dx[i]
    y = dy[i]
    if 0 <= start[0] + y <= H - 1 and 0 <= start[1] + x <= W - 1:
        tmp = items[start[0] + y][start[1] + x]
        if tmp == ".":
            que.append((start[0] + y, start[1] + x))
            prev[start[0] + y][start[1] + x] = True
k = K
while len(que) != 0:
    q = que.popleft()
    a = q[0]
    b = q[1]
    if abs(start[0] - a) + abs(start[1] - b) > K:
        continue
    c = min(min(a, H - 1 - a), min(b, W - 1 - b))
    if c < diff:
        diff = c
        p = (a, b)

    for i in range(4):
        x = dx[i]
        y = dy[i]
        if 0 <= a + y <= H - 1 and 0 <= b + x <= W - 1:
            if prev[a + y][b + x]:
                continue
            tmp = items[a + y][b + x]
            if tmp == ".":
                que.append((a + y, b + x))
                prev[a + y][b + x] = True

ans = 1
if diff == 0:
    print(ans)
else:
    print(ans + (K - 1 + diff) // K)


### FIXED CODE ###

H, W, K = map(int, input().split())
items = []

start = []
diff = float("inf")
p = []
prev = [[False] * W for _ in range(H)]
for i in range(H):
    items.append(list(input()))
    for j in range(W):
        s = items[i][j]
        if s == "S":
            start = [i, j]
            diff = min(diff, min(i, H - 1 - i, min(j, W - 1 - j)))
            p = [i, j]
            prev[i][j] = True

from collections import deque

que = deque([])

dx = [-1, 0, 0, 1]
dy = [0, 1, -1, 0]

for i in range(4):
    x = dx[i]
    y = dy[i]
    if 0 <= start[0] + y <= H - 1 and 0 <= start[1] + x <= W - 1:
        tmp = items[start[0] + y][start[1] + x]
        if tmp == ".":
            que.append((start[0] + y, start[1] + x))
            prev[start[0] + y][start[1] + x] = True
k = K
while len(que) != 0:
    q = que.popleft()
    a = q[0]
    b = q[1]
    if abs(start[0] - a) + abs(start[1] - b) > K:
        continue
    c = min(min(a, H - 1 - a), min(b, W - 1 - b))
    if c < diff:
        diff = c
        p = (a, b)

    for i in range(4):
        x = dx[i]
        y = dy[i]
        if 0 <= a + y <= H - 1 and 0 <= b + x <= W - 1:
            if prev[a + y][b + x]:
                continue
            tmp = items[a + y][b + x]
            if tmp == ".":
                que.append((a + y, b + x))
                prev[a + y][b + x] = True

ans = 1
if diff == 0:
    print(ans)
else:
    print(ans + (K - 1 + diff) // K)
### BUGGY CODE ###

Matches = {num: c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}

def solve(N, M, As):
    Ms = {num: c for num, c in Matches.items() if num in As}
    dp = [-1 for _ in range(N + 1)]
    dp[0] = 0
    for n in range(N + 1):
        for num, c in Ms.items():
            if n - c >= 0:
                if dp[n - c] == -1:
                    continue
                if dp[n - c] == 0:
                    dp[n] = max(num, dp[n])
                else:
                    dp[n] = max(int(str(dp[n - c]) + str(num)),
                                int(str(num) + str(dp[n - c])),
                                dp[n])
    return dp[N]

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, M, As))


### FIXED CODE ###

Matches = {num: c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}


def solve(N, M, As):
    dp = [-1 for _ in range(N + 1)]
    dp[0] = 0
    for a in sorted(As, reverse=True):
        c = Matches[a]
        for i in range(N - c + 1):
            if dp[i] == -1:
                continue
            dp[i + c] = max(dp[i+c],
                            dp[i] * 10 + a)
    return dp[N]

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, M, As))
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
B=[0]*M
C=[0]*M
D=0
for i in range(M):
    B[i], C[i] = map(int, input().split())
    D +=B[i]
    A += [C[i]]*B[i]

A.sort(reverse = True)
#print(A)
print(sum(A[:N]))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)
D = []
sum_B=0
for B, C in BC:
    D += [C] * B
    sum_B += B
    if sum_B>N:
        break

A+=D
A.sort(reverse = True)
print(sum(A[:N]))
### BUGGY CODE ###

import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
asort = sorted(a)
bsort = sorted(b)
csort = sorted(c)
res = 0
for ai in a:
    bindex = bisect.bisect_right(bsort, ai)
    if bindex == n:
        continue
    for bi in bsort[bindex:]:
        cindex = bisect.bisect_right(csort, bi)
        if cindex == n:
            continue
        res += n-cindex
print(res)

### FIXED CODE ###

import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
bsort = sorted(b)
csort = sorted(c)
res = 0
asum = [0] * n
bsum = [0] * n
for i in range(n):
    asum[i] = n - bisect.bisect_right(bsort, a[i])
for i in range(n):
    bsum[i] = n - bisect.bisect_right(csort, b[i])
bsum.sort()
total = 0
for i in range(n):
    total += bsum[i]
    bsum[i] = total
res = 0
for i in range(n):
    if asum[i] != 0:
        res += bsum[asum[i] -1]
print(res)
### BUGGY CODE ###

# 2019-11-16 21:01:15(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
from scipy.misc import comb # float
# import numpy as np 


mod = 10 ** 9 + 7

def main():
    x, y = [int(x) for x in sys.stdin.readline().split()]
    # n(+1, +2), m(+2, +1)
    n, m = (2 * y - x) / 3, (2 * x - y) / 3

    if n != abs(int(n)) or m != abs(int(m)):
        print(0)
        sys.exit()
    else:
        n, m = int(n), int(m)
        ans = comb(n+m, n, exact=True) % mod
        print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

# 2019-11-16 21:01:15(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
from functools import reduce
import operator as op
# from scipy.misc import comb # float
# import numpy as np 


mod = 10 ** 9 + 7

def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    
    return result


def main():
    x, y = [int(x) for x in sys.stdin.readline().split()]
    # n(+1, +2), m(+2, +1)
    n, m = (2 * y - x) / 3, (2 * x - y) / 3

    if n != abs(int(n)) or m != abs(int(m)):
        print(0)
        sys.exit()
    else:
        n, m = int(n), int(m)
        ans = comb(n+m, n) % mod
        print(ans)

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

mod = 10**9+7
S = [int(x) if x != "?" else -1 for x in input()][::-1]

dp = [[0] * 13 for i in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    if S[i] == -1:
        for d in range(10):
            for j in range(13):
                dp[i+1][(j+d*10**i) % 13] += dp[i][j]
    else:
        d = S[i]
        for j in range(13):
            dp[i+1][(j+d*10**i) % 13] += dp[i][j]

    # for k in range(13):
    #     dp[i+1][k] = dp[i+1][k] % mod

    # print(dp)

print(dp[len(S)][5] % mod)


### FIXED CODE ###

mod = 10**9+7
S = [int(x) if x != "?" else -1 for x in input()]

dp = [[0] * 13 for i in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    if S[i] == -1:
        for d in range(10):
            for j in range(13):
                dp[i+1][(j*10+d) % 13] += dp[i][j]
    else:
        d = S[i]
        for j in range(13):
            dp[i+1][(j*10+d) % 13] += dp[i][j]

    for k in range(13):
        dp[i+1][k] = dp[i+1][k] % mod

    # print(dp)

print(dp[len(S)][5])
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def solve():
    MOD = 10**9+7
    N = int(input())
    A_L = [int(x) for x in input().split()]
    ans = 0
    for i, ai in enumerate(A_L):
        for j in range(i+1, N):
            aj = A_L[j]
            ans = (ans + ai * aj) % MOD

    print(ans)


solve()


### FIXED CODE ###

import sys

input = sys.stdin.readline


def solve():
    MOD = 10**9+7
    N = int(input())
    A_L = tuple(int(x) for x in input().split())
    cum_a_l = [0] * N
    cum_a_l[0] = A_L[0]
    for i in range(1, N):
        cum_a_l[i] = (cum_a_l[i-1] + A_L[i]) % MOD
    ans = 0

    for i in range(N-1, 0, -1):
        ans = (ans + cum_a_l[i-1]*A_L[i] % MOD) % MOD
    print(ans)


solve()