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

import itertools
from collections import deque
from sys import stdin
input = stdin.readline


def main():
  H, W = list(map(int, input().split()))

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    is_visited = [[0]*W for _ in range(H)]
    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '#':
        return
      is_visited[now_h][now_w] = 1
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           is_visited[next_h][next_w] or \
           M[next_h][next_w] == '#':
          continue

        dist[next_h][next_w] = dist[now_h][now_w] + 1
        max_ = max(max_, dist[next_h][next_w])
        q.append((next_h, next_w))
    return max_

  max_ = 0
  for h in range(H):
    for w in range(W):
      if M[h][w] == '.':
        max_ = max(bfs((h, w)), max_)

  print(max_)


if(__name__ == '__main__'):
  main()


### FIXED CODE ###

import itertools
from collections import deque
from sys import stdin
input = stdin.readline


def main():
  H, W = list(map(int, input().split()))

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (dist[next_h][next_w] != float('inf')) or \
           M[next_h][next_w] == '#':
          continue

        temp = dist[now_h][now_w] + 1
        dist[next_h][next_w] = temp
        if max_ < temp:
          max_ = temp
        q.append((next_h, next_w))
    return max_

  max_ = 0
  for h in range(H):
    for w in range(W):
      if M[h][w] == '.':
        max_ = max(bfs((h, w)), max_)

  print(max_)


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

n, k = map(int, input().split())
hs = list(map(int, input().split()))
min_cost = [float('inf')] * n
min_cost[0] = 0
for i in range(1, n):
    min_cost[i] = min([min_cost[i-j] + abs(hs[i] - hs[i-j]) for j in range(1, k+1) if i-j >= 0])
print(min_cost[n-1])


### FIXED CODE ###

n, k = map(int, input().split())
hs = list(map(int, input().split()))
min_cost = [float('inf')] * n
min_cost[0] = 0
for i in range(1, n):
    min_cost[i] = min([min_cost[i-j] + abs(hs[i] - hs[i-j]) for j in range(1, k+1) if i-j >= 0])
print(min_cost[n-1])
### BUGGY CODE ###

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

for i in range(1, N+1):
    k=A.count(i)
    print(k)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
cnt=[0]*N

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

for k in range(N):
    print(cnt[k])
### BUGGY CODE ###

N=int(input())
A = list(map(int, input().split()))
for i in range(1,N+1):
    print(A.count(i))

### FIXED CODE ###

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

B=sorted(A)

def histogram_sorted(data):
    table = []
    prev = data[0] 
    c = 1
    for i in range(1,len(data)):
        if prev == data[i]:
            c=c+1
        else:
            table.append([prev,c])
            prev = data[i]
            c = 1
    table.append([prev,c])
    return table

X = histogram_sorted(B)

X.append([0,0])

c=0
for i in range(1,N+1):
    if X[c][0] == i:
        print(X[c][1])
        c = c+1
    else:
        print(0)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict
N, M = map(int, input().split())
dic = defaultdict(list)
P_X = [None] * M
for _ in range(M):
  p, x = input().split()
  p, x = int(p), int(x)
  P_X[_] = (p, x)
  dic[p].append(x)
for key in dic:
  dic[key].sort()
for i in range(M):
  print(str(P_X[i][0]).zfill(6) + str((dic[P_X[i][0]].index(P_X[i][1]) + 1)).zfill(6))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect as bs
from collections import defaultdict
N, M = map(int, input().split())
dic = defaultdict(list)
P_X = [None] * M
for _ in range(M):
  p, x = input().split()
  p, x = int(p), int(x)
  P_X[_] = (p, x)
  dic[p].append(x)
for key in dic:
  dic[key].sort()
for i in range(M):
  print(str(P_X[i][0]).zfill(6) + str(bs.bisect_left(dic[P_X[i][0]], P_X[i][1]) + 1).zfill(6))
### BUGGY CODE ###

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

for _ in range(K):
    b = [0 for _ in range(n+1)]
    for i,a in enumerate(A):
        b[max(0, i-a)] += 1
        b[min(n, i+a+1)] -= 1

    for i in range(n):
        b[i+1] += b[i]

    A = b[:-1]
    if all(a == n for a in A):
        break
print(*A)

### FIXED CODE ###

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

for _ in range(K):
    b = [0 for _ in range(n+1)]
    for i,a in enumerate(A):
        b[max(0, i-a)] += 1
        b[min(n, i+a+1)] -= 1

    for i in range(n):
        b[i+1] += b[i]

    A = b[:-1]
    if all(a == n for a in A):
        break
print(*A)
### BUGGY CODE ###

n = int(input())
t = []
for i in range(n):
    a = input()
    if(a in t):
        a = 1
    else:
        t.append(a)
print(len(t))

### FIXED CODE ###

n = int(input())
t = []
for i in range(677):
    t.append([])
x = n
for i in range(n):
    a = input()
    if(len(a) < 4):
        if(a in t[0]):
            x -= 1
        else:
            t[0].append(a)
    else:
        p = ord(a[0])*26+ord(a[1])-2618
        if(a[2:] in t[p]):
            x -= 1
        else:
            t[p].append(a[2:])
print(x)
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.insert(0,0)
X = {i:0 for i in range(-2*N,4*N+2)}
k = 0
while k<K:
    for i in range(1,N+1):
        d = A[i]
        X[2*i-2*d-1] += 1
        X[2*i+2*d+1] -= 1
    for i in range(-2*N+1,4*N+2):
        X[i] += X[i-1]
    for i in range(1,N+1):
        A[i] = X[2*i]
    X = {i:0 for i in range(-2*N,4*N+2)}
    cnt = 0
    for i in range(1,N+1):
        cnt += A[i]
    if cnt==N*N:
        break
    k += 1
print(*A[1:])

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
cnt = 0
while cnt<K:
    B = [0 for _ in range(N+1)]
    for i in range(N):
        a = A[i]
        B[max(i-a,0)] += 1
        B[min(i+a,N-1)+1] -= 1
    for i in range(1,N+1):
        B[i] += B[i-1]
    A = B[:N]
    flag = 0
    for i in range(N):
        if A[i]<N:
            flag = 1
            break
    if flag==0:break
    cnt += 1
print(*A)
### BUGGY CODE ###

import numpy as np

def dfs(A, a, n, ans):
  if len(A) == n:
    tmp = A + a
    if sum(tmp % 2) < len(A):
      ans += 1
    return ans
  
  for i in range(-1, 2):
    A = np.append(A, i)
    ans = dfs(A, a, n, ans)
    A = np.delete(A, -1)
    
  return ans

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

print(dfs(np.array([]), a, n, 0))

### FIXED CODE ###

import numpy as np

def dfs(A, a, n, ans):
  if len(A) == n:
    tmp = np.array(A) + a
    if sum(tmp % 2) < len(A):
      ans += 1
    return ans
  
  for i in range(-1, 2):
    A.append(i)
    ans = dfs(A, a, n, ans)
    A.pop()
    
  return ans

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

print(dfs([], a, n, 0))
### BUGGY CODE ###

s = input()
sl = len(s)
s = list(s)
while True:
  for i in range(len(s)-1):
    if s[i] != s[i+1]:
      s.pop(i+1)
      s.pop(i)
      break
  else:
    break
print(sl - len(s))
  

### FIXED CODE ###

s = input()

t = s[0]
for i in s[1:]:
  if not t:
    t=i
    continue
  if i != t[-1]:
    t=t[:-1]
  else:
    t+=i

print(len(s) - len(t))
### BUGGY CODE ###

import math
h, w, d = map(int, input().split())
a = [[0, 0] for i in range(h*w+1)]
for i in range(h):
    ai = list(map(int, input().split()))
    for j in range(w):
        a[ai[j]] = [i+1, j+1]

def dist(p1, p2):
    return abs(a[p1][0] - a[p2][0]) + abs(a[p1][1] - a[p2][1])

MAX_LOG = math.ceil(math.log2(h*w))
b = [[0 for j in range(MAX_LOG)] for i in range(h*w+1)]
for j in range(MAX_LOG):
    for i in range(1, h*w+1):
        if j == 0:
            if i + d < h*w + 1:
                b[i][j] = dist(i, i + d)
        elif i + d*(1<<j) < h*w + 1:
            b[i][j] = b[i][j-1] + b[i + d*(1<<(j-1))][j-1]

# for bi in b:
#     print(bi)

def query(l, bit):
    if bit == 0:
        return 0
    j = 0
    while (bit>>j) & 1 == 0:
        j += 1

    return b[l][j] + query(l + d * (1<<j), bit ^ (1<<j))


q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(query(l, (r-l)//d))


### FIXED CODE ###

import math
h, w, d = map(int, input().split())
a = [[0, 0] for i in range(h*w+1)]
for i in range(h):
    ai = list(map(int, input().split()))
    for j in range(w):
        a[ai[j]] = [i+1, j+1]

def dist(p1, p2):
    return abs(a[p1][0] - a[p2][0]) + abs(a[p1][1] - a[p2][1])

# MAX_LOG = math.ceil(math.log2(h*w))
MAX_LOG = 18
b = [[0 for j in range(MAX_LOG)] for i in range(h*w+1)]
for j in range(MAX_LOG):
    for i in range(1, h*w+1):
        if j == 0:
            if i + d < h*w + 1:
                b[i][j] = dist(i, i + d)
        elif i + d*(1<<j) < h*w + 1:
            b[i][j] = b[i][j-1] + b[i + d*(1<<(j-1))][j-1]

# for bi in b:
#     print(bi)

def query(l, bit):
    if bit == 0:
        return 0
    j = 0
    while (bit>>j) & 1 == 0:
        j += 1

    return b[l][j] + query(l + d * (1<<j), bit ^ (1<<j))


q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(query(l, (r-l)//d))
### BUGGY CODE ###

def main():
    N , M, K = map(int, input().split())
    A_list = [A for A in input().split()]
    B_list = [B for B in input().split()]
    A_list = list(map(int, A_list))
    B_list = list(map(int, B_list))

    al = [0]
    bl = [0]

    for i in range(N) :
        al.append(al[i] + A_list[i])
    for i in range(M) :
        bl.append(bl[i] + B_list[i])
    #print("al = %s" % al)
    #print("bl = %s" % bl)
    re = M
    book = 0

    for i in range(N+1) :
        re = M
        if al[i] > K :
            break
        for j in range(M+1) :
            if bl[re] <= K - al[i] :
                break
            else :
                re -= 1

        book = max(book, i + re)

    print(book)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N , M, K = map(int, input().split())
    A_list = list(map(int, input().split()))
    B_list = list(map(int, input().split()))

    al = [0]
    bl = [0]

    for i in range(N) :
        al.append(al[i] + A_list[i])
    for i in range(M) :
        bl.append(bl[i] + B_list[i])
    #print("al = %s" % al)
    #print("bl = %s" % bl)
    book = 0
    re = M

    for i in range(N+1) :
        if al[i] > K :
            break
        #for j in range(M+1) :
        #    if bl[re] <= K - al[i] :
        #        break
        #    else :
        #        re -= 1
        while bl[re] > K - al[i] :
            re -= 1

        book = max(book, i + re)

    print(book)


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

s = str(input())[::-1]
sum_of_digits = 0
cnt = [0] * 2019

cnt[0] = 1
d = 1
for i, c in enumerate(s, start=1):
    sum_of_digits *= 1
    d = 10 ** (i-1)
    d %= 2019
    sum_of_digits += d * int(c)
    sum_of_digits %= 2019
    cnt[sum_of_digits] += 1
    #print(sum_of_digits)

print(sum([i*(i-1)//2 for i in cnt]))

### FIXED CODE ###

s = str(input())[::-1]
sum_of_digits = 0
cnt = [0] * 2019

cnt[0] = 1
d = 1
for c in s:
    d *= 10
    d %= 2019
    sum_of_digits += d * int(c)
    sum_of_digits %= 2019
    cnt[sum_of_digits] += 1

print(sum([i*(i-1)//2 for i in cnt]))
### BUGGY CODE ###

import numpy as np
from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
# Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]
Cost = np.full((H,W),MAX_COST)

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

# used = set()
five_five = [ (i,j) for i in range(-2,3,1) for j in range(-2,3,1) ]
# print(five_five)

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in five_five:
		# print(i,j)
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.':
				if (j == 0 and (i==1 or i==-1)) or (i==0 and (j==1 or j==-1)):
					if c < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c
						deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
				elif c + 1 < Cost[h+i][w+j]:
					Cost[h+i][w+j] = c + 1
					deq.append((h+i,w+j,Cost[h+i][w+j]))
					# print("updr ", h+i,w+j,Cost[h+i][w+j])

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])

### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

walk=[(1,0),(0,1),(-1,0),(0,-1)]

# used = set()

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in walk:
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.' and c < Cost[h+i][w+j]:
				Cost[h+i][w+j] = c
				# print("updl ", i,j,h+i,w+j,c)
				deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
	for i in range(-2,3,1):
		for j in range(-2,3,1):
			# print(i,j)
			if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
				if S[h+i][w+j] == '.':
					if c + 1 < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c + 1
						deq.append((h+i,w+j,Cost[h+i][w+j]))
						# print("updr ", h+i,w+j,Cost[h+i][w+j])

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])
### BUGGY CODE ###

n = int(input())
lst = []

for i in range(n):
    num = input().split()
    if num in lst:
        lst.remove(num)
    else:
        lst.append(num)

print(len(lst))

### FIXED CODE ###

n = int(input())
se = set()

for i in range(n):
    num = int(input())
    if num in se:
        se.remove(num)
    else:
        se.add(num)

print(len(se))
### BUGGY CODE ###

from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
    combinations_with_replacement,  # 重複あり組み合わせ
)

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


N = int(input())
ans = 0
for v in product(range(1, N+1), repeat=3):
    ans += gcd_list(v)

print(ans)

### FIXED CODE ###

from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
    combinations_with_replacement,  # 重複あり組み合わせ
)

import fractions, math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)


N = int(input())
ans = 0
for i, j, k in combinations_with_replacement(range(1, N+1), 3):
    if i==j==k:
        ans += i
    elif i==j:
        ans += math.gcd(i, k)*3
    elif j==k:
        ans += math.gcd(j, i)*3
    elif i==k:
        ans += math.gcd(i, j)*3
    else:
        ans += gcd_list([i, j, k])*6
print(ans)
### BUGGY CODE ###

num = int(input())
temp = num
ans = 1
while temp > 10:
    temp %= 10
# print(temp)
if temp in [1, 3, 7, 9]:
    sa = 7
    while True:
        if sa % num == 0:
            print(ans)
            break
        else:
            sa *= 10
            sa += 7
            ans += 1
else:
    print(-1) 

### FIXED CODE ###

num = int(input())
temp = num
ans = 1
while temp > 10:
    temp %= 10
# print(temp)
if temp in [1, 3, 7, 9]:
    sa = 7
    while True:
        if sa % num == 0:
            print(ans)
            break
        else:
            sa *= 10
            sa += 7
            sa %= num
            ans += 1
else:
    print(-1)
### BUGGY CODE ###

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

kous = list(map(make_divisors, As))
all = []
for v in kous:
    all += v
all = sorted(list(set(all)), reverse=True)

counts = []
for v in all:
    count = 0
    for a in As:
        if v in make_divisors(a):
            count += 1
    counts.append(count)


ans = 1
for i in range(len(counts)):
    if counts[i]>=N-1:
        ans = all[i]
        break
print(ans)

### FIXED CODE ###

import sys
if sys.version_info.minor >= 5:
    from math import gcd
else:
    from fractions import gcd



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

left_gcds = [gcd(As[0], As[0])]
for i in range(1, len(As)):
    left_gcds.append(gcd(left_gcds[i-1], As[i]))

right_gcds = [gcd(As[-1], As[-1])]
for i in range(1, len(As)):
    right_gcds.append(gcd(right_gcds[i-1], As[-(i+1)]))
right_gcds.reverse()

gcds = []
for i in range(N):
    if i == 0:
        gcds.append(right_gcds[1])
    elif i == N-1:
        gcds.append(left_gcds[-2])
    else:
        gcds.append(gcd(left_gcds[i-1], right_gcds[i+1]))
print(max(gcds))
### BUGGY CODE ###

import copy

n = int(input())
a_lst = []
for i in range(n):
    a = int(input())
    a_lst.append(a)

sorted_a_lst = sorted(a_lst)
max_a = sorted_a_lst[-1]

for a in a_lst:
    if a == max_a:
        tmp = copy.copy(a_lst)
        tmp.remove(a)
        tmp = sorted(tmp)
        print(tmp[-1])
    else:
        print(max_a)

### FIXED CODE ###

n = int(input())
a_lst = []
for i in range(n):
    a = int(input())
    a_lst.append(a)

sorted_a_lst = sorted(a_lst)
max_a = sorted_a_lst[-1]

for a in a_lst:
    if a == max_a:
        print(sorted_a_lst[-2])
    else:
        print(max_a)
### BUGGY CODE ###

import sys
pin=sys.stdin.readline

S=pin()[:-1]
Q=int(pin())
now=1

for i in range(Q):
  D=pin().split()
  T=0
  F=0
  C=""
  if len(D)==1:
    T=int(D[0])
  else:
    T=int(D[0])
    F=int(D[1])
    C=D[2]
  if T==1:
    now*=-1
  else:
    if F==1:
      if now==1:
        S=C+S
      else:
        S=S+C
    else:
      if now==1:
        S=S+C
      else:
        S=C+S
if now==1:
  print(S)
else:
  print(S[::-1])


### FIXED CODE ###

import sys
pin=sys.stdin.readline

S=pin()[:-1]
Q=int(pin())
now=1
ans1=""
ans2=""
for i in range(Q):
  D=pin().split()
  T=0
  F=0
  C=""
  if len(D)==1:
    T=int(D[0])
  else:
    T=int(D[0])
    F=int(D[1])
    C=D[2]
  if T==1:
    now*=-1
  else:
    if F==1:
      if now==1:
        ans1=C+ans1
      else:
        ans2=ans2+C
    else:
      if now==1:
        ans2=ans2+C
      else:
        ans1=C+ans1
if now==1:
  print(ans1+S+ans2)
else:
  print(ans2[::-1]+S[::-1]+ans1[::-1])
### BUGGY CODE ###

X,K,D = map(int,input().split())
X = abs(X)
a = int(X/D)
if a < K:
        K -= a
        X -= a*D

if K*D <= X:
    X -= K*D
else:
    for i in range(K):
        if X > 0:
            X -= D
        else:
            X += D
print(abs(X))

### FIXED CODE ###

X,K,D = map(int,input().split())
X = abs(X)
a = int(X/D)
if a < K:
        K -= a
        X -= a*D

if K*D <= X:
    X -= K*D
else:
    K %= 2
    for i in range(K):
        if X > 0:
            X -= D
        else:
            X += D
print(abs(X))
### BUGGY CODE ###

import math
if __name__ == "__main__":
    # K>=200 なので3重ループは間に合わなそう
    K = int(input())
    gcd_dic = {}

    for i in range(1, K+1):
        for j in range(i, K+1):
            gcd_dic[(i,j)] = math.gcd(i, j)
    #print(gcd_dic)
    ans = 0
    for i in range(1, K+1):
        for j in range(1, K+1):
            ij_gcd = gcd_dic[(min(i, j), max(i,j))]
            #print(ij_gcd)
            for k in range(1, K+1):
                ans +=  gcd_dic[(min(ij_gcd, k), max(ij_gcd,k))]
    print(ans)




### FIXED CODE ###

import math
if __name__ == "__main__":
    # K>=200 なので3重ループは間に合わなそう
    K = int(input())
    gcd_dic = {}

    for i in range(1, K+1):
        for j in range(i, K+1):
            gcd_dic[(i,j)] = math.gcd(i, j)

    # #print(gcd_dic)
    # ans = 0
    # for i in range(1, K+1):
    #     for j in range(1, K+1):
    #         ij_gcd = gcd_dic[(min(i, j), max(i,j))]
    #         print(ij_gcd)
    #         print("(i,j):({},{}), {}".format(i, j, ij_gcd))
    #         for k in range(1, K+1):
    #             print("  k:{}, {}".format(k, gcd_dic[(min(ij_gcd, k), max(ij_gcd,k))]))
    #             ans += gcd_dic[(min(ij_gcd, k), max(ij_gcd, k))]

    ans = 0
    for i in range(1, K+1):
        for j in range(1, K+1):
            ij_gcd = gcd_dic[(min(i, j), max(i,j))]
            #print(ij_gcd)
            #print("(i,j):({},{}), {}".format(i, j, ij_gcd))
            if ij_gcd == 1:
                ans += K
            else:
                for k in range(1, K+1):
                    #print("  k:{}, {}".format(k, gcd_dic[(min(ij_gcd, k), max(ij_gcd,k))]))
                    ans += gcd_dic[(min(ij_gcd, k), max(ij_gcd, k))]
    # ans = 0
    # for i in range(1, K+1):
    #     for j in range(1, K+1):
    #         ij_gcd = gcd_dic[(min(i, j), max(i,j))]
    #         print("(i,j):({},{}), {}".format(i, j, ij_gcd))
    #         for k in range(1, ij_gcd+1):
    #             # k <= ij_gcd
    #             print("  k:{}, {}".format(k, gcd_dic[k, ij_gcd]))
    #             ans +=  gcd_dic[k, ij_gcd]
    #         # k > ij_gcd なら
    #         print("  k//id_gcd:{}".format(K // ij_gcd))
    #         print("  ans += {}".format((K // ij_gcd - 1) * ij_gcd))
    #         print("  ans += {}".format(K - ij_gcd - K // ij_gcd + 1))
    #         ans += (K // ij_gcd - 1) * ij_gcd 
    #         ans += K - ij_gcd - K // ij_gcd + 1 # K=10, ji_gcd=4のとき，6, 10=2 を逃す
    print(ans)
### BUGGY CODE ###

n=int(input())
mod=int(1e9)+7
l=[int(x) for x in input().split()]
sum1=0
for i in range(n-1):
    for j in range(i+1,n,1):
        prod=(l[i]*l[j])%mod
        sum1=(sum1%mod+prod%mod)%mod
print(sum1)


### FIXED CODE ###

n=int(input())
mod=int(1e9)+7
l=[int(x) for x in input().split()]
sum1=0
sum2=0
for i in range(n):
    sum2=(sum2%mod+l[i]%mod)%mod
for i in range(n-1):
    sum2=sum2-l[i]
    x=(sum2%mod*(l[i]%mod))%mod
    sum1=(sum1%mod+(x%mod))%mod
print(sum1)
### BUGGY CODE ###

# Traveling Plan
n = int(input())
a = [0]
a += list(map(int, input().split()))
a += [0]
for i in range(n):
    ans = 0
    for j in range(n+1):
        if j == i:
            ans += abs(a[j]-a[j+2])
        elif j == i+1:
            pass
        else:
            ans += abs(a[j]-a[j+1])
    print(ans)


### FIXED CODE ###

# Traveling Plan
n = int(input())
a = [0]
a += list(map(int, input().split()))
a += [0]
total = 0
for i in range(n+1):
    total += abs(a[i]-a[i+1])
for i in range(n):
    p = total -(abs(a[i]-a[i+1]) + abs(a[i+1]-a[i+2])) + abs(a[i]-a[i+2])
    print(p)
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
I = []
for i in range(N - 1):
    if H[i] >= H[i + 1]:
        I.append(H[i])
I.append(H[N - 1])
N = len(I)
for i in range(N):
    for j in range(i + 1, N):
        if I[i] > I[j] + 1:
            print('No')
            quit()
print('Yes')

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
I = [H[i + 1] - H[i] for i in range(N - 1)]
N = len(I)
for i in range(N):
    if I[i] >= 0:
        continue
    elif I[i] < -1:
        print('No')
        quit()
    else:
        if i == N - 1:
            continue
        for j in range(i + 1, N):
            if I[j] >= 1:
                break
            elif I[j] <= -1:
                print('No')
                quit()
            else:
                continue
print('Yes')