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

import numpy as np
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0
for i in range(h):
    for j in range(w):
        q = deque()
        q.append([i, j, 0])
        if s[i][j] == '#': continue
        visited = np.zeros((h + 5, w + 5))
        while q:
            x, y, z = q.popleft()
            if z > ans: ans = z
            visited[x][y] = True
            for dx, dy in dirr:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
from collections import deque

h, w = [int(item) for item in input().split()]
field = []
field.append("#" * (w + 2))
for i in range(h):
    field.append("#" + input().rstrip() + "#")
field.append("#" * (w + 2))


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if field[i][j] == "#":
            continue
        dist = [[-1] * (w + 2) for _ in range(h + 2)]
        dist[i][j] = 0
        dq = deque()
        dq.append((i, j, 0))
        while dq:
            x, y, d = dq.popleft()
            if field[x+1][y] == "." and dist[x+1][y] == -1:
                dist[x+1][y] = d+1
                dq.append((x+1, y, d+1))
            if field[x][y+1] == "." and dist[x][y+1] == -1:
                dist[x][y+1] = d+1
                dq.append((x, y+1, d+1))
            if field[x-1][y] == "." and dist[x-1][y] == -1:
                dist[x-1][y] = d+1
                dq.append((x-1, y, d+1))
            if field[x][y-1] == "." and dist[x][y-1] == -1:
                dist[x][y-1] = d+1
                dq.append((x, y-1, d+1))
        for line in dist:
            ans = max(ans, max(line))
        
print(ans)
### BUGGY CODE ###

import sys


def input():
    return sys.stdin.readline()[:-1]


H, W = map(int, input().split())

A = [[1 if s == "#" else 0 for s in input()] for i in range(H)]

lu = [[1<<20 for i in range(W + 2)] for j in range(H + 2)]

for ii in range(H * W):
    i = ii // W + 1
    j = ii % W + 1
    lu[i][j] = min(lu[i - 1][j], lu[i][j - 1]) + 1
    if A[i - 1][j - 1]:
        lu[i][j] = 0
    elif j < W and A[i - 1][j]:
        lu[i][j] = 1

for ii in range(H * W):
    i = H - ii // W
    j = W - ii % W
    lu[i][j] = min(lu[i + 1][j] + 1, lu[i][j + 1] + 1, lu[i][j])

dist = max(sum([l[1:-1] for l in lu[1:-1]], []))
print(dist)


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline()[:-1]


H, W = map(int, input().split())

A = [[1 if s == "#" else 0 for s in input()] for i in range(H)]

lu = [[1<<20] * (W+2) for j in range(H + 2)]

for ii in range(H * W):
    i = ii // W + 1
    j = ii % W + 1
    lu[i][j] = min(lu[i - 1][j], lu[i][j - 1]) + 1
    if A[i - 1][j - 1]:
        lu[i][j] = 0
    elif j < W and A[i - 1][j]:
        lu[i][j] = 1

for ii in range(H * W):
    i = H - ii // W
    j = W - ii % W
    lu[i][j] = min(lu[i + 1][j] + 1, lu[i][j + 1] + 1, lu[i][j])

dist = []
[dist.extend(l[1:-1]) for l in lu[1:-1]]
print(max(dist))
### BUGGY CODE ###

import sys
from itertools import accumulate
import numpy as np


def solve():
    N, K, *P = map(int, sys.stdin.read().split())
    n = np.convolve(np.array(P), np.ones(K), mode='valid').argmax()
    cusum = tuple(accumulate(range(1000+1)))
    return sum(cusum[i] / i for i in P[n:n+K])


if __name__ == "__main__":
    answer = solve()
    print(answer)


### FIXED CODE ###

import sys
from itertools import accumulate


def solve():
    N, K = map(int, sys.stdin.readline().split())
    cusum_p = (0,) + tuple(accumulate(map(int, sys.stdin.read().split())))
    return (max(i - j for i, j in zip(cusum_p[K:], cusum_p[:-K])) + K) / 2


if __name__ == "__main__":
    answer = solve()
    print(answer)
### BUGGY CODE ###

n = int( input() )
da = []
ans = 0
for i in range(n):
    s = input()
    d = {}
    for item in s:
        if item in d:
            d[item] += 1
        else:
            d[item] = 1

    for d1 in da:
        if d1 == d:
            ans += 1
    
    da.append(d)


print(ans)

### FIXED CODE ###

n = int( input() )
dd = {}
ans = 0
for i in range(n):
    s = ''.join( sorted( input() ))
    if s in dd:
        ans += dd[s]
        dd[s] += 1
    else:
        dd[s] = 1

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

n, k, c = map(int, input().split())
s = input()
l = len(s) - 1
i = 0
lb = []
le = []
while i < len(s) and len(lb) < k:
    # print(i)
    if s[i] == 'o':
        lb.append(i)
        i += c + 1
        continue
    i += 1

while l > -1 and len(le) < k:
    if s[l] == 'o':
        le.append(l)
        l -= (c + 1)
        continue
    l -= 1

for j in range(0, len(lb)):
    if lb[j] in le:
        print(lb[j]+1)

### FIXED CODE ###

n, k, c = map(int, input().split())
s = input()
l = len(s) - 1
i = 0
lb = []
le = []
while i < len(s) and len(lb) < k:
    if s[i] == 'o':
        lb.append(i)
        i += c + 1
        continue
    i += 1

while l > -1 and len(le) < k:
    if s[l] == 'o':
        le.append(l)
        l -= (c + 1)
        continue
    l -= 1

le.sort()
for j in range(0, len(lb)):
    if lb[j] == le[j]:
        print(lb[j]+1)
### BUGGY CODE ###

#import time

#t1=time.time()
n=int(input())
s=list(input())
info=[]
for i in range(10):
    for j in range(10):
        for k in range(10):
            info.append(str(i)+str(j)+str(k))
ans=0
kind=0
while kind<=999:
    point=0
    check=info[kind]
    for i in range(n):
        if point==0:  
            if check[0]==s[i]:
                point+=1
                continue
        if point==1:
            if check[1]==s[i]:
                point+=1
                continue
        if point==2:
            if check[2]==s[i]:
                point+=1
                break
    if point==3:
        ans+=1
        #print(info[kind])
    kind+=1
print(ans)
#t2=time.time()
#print(t2-t1)

### FIXED CODE ###

#import time

#t1=time.time()
n=int(input())
s=list(input())
info=[]
for i in range(10):
    for j in range(10):
        for k in range(10):
            info.append(str(i)+str(j)+str(k))
ans=0
kind=0
while kind<=999:
    point=0
    check=info[kind]
    for i in range(n):
        if point==0:  
            if check[0]==s[i]:
                point+=1
                continue
        if point==1:
            if check[1]==s[i]:
                point+=1
                continue
        if point==2:
            if check[2]==s[i]:
                point+=1
                break
    if point==3:
        ans+=1
        #print(info[kind])
    kind+=1
print(ans)
#t2=time.time()
#print(t2-t1)
### BUGGY CODE ###

# 1からNまでの数字それぞれの約数を求める
# Nから(大きい値から)見ていき、1であれば入れる
# 数字iを入れた場合、iの約数の数を+1
# それぞれの数はdictで保持する

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

ans = [0 for _ in range(N)]

ans_num = 0
for i in range(N):
    tmp = N - i
    s = 0
    for j in range(tmp, N):
        if (j+1) % tmp == 0:
            s += ans[j]

    if s % 2 != A[tmp - 1]:
        ans[tmp - 1] = 1
        ans_num += 1


print(ans_num)
ans_list = ""
for i in range(N):
    if ans[i] == 1:
        ans_list += str(i + 1)
        if i != N - 1:
            ans_list += " "

print(ans_list)

### FIXED CODE ###

# 1からNまでの数字それぞれの約数を求める
# Nから(大きい値から)見ていき、1であれば入れる
# 数字iを入れた場合、iの約数の数を+1
# それぞれの数はdictで保持する

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

ans = [0 for _ in range(N)]

ans_num = 0
ans_list = ""
for i in range(N):
    tmp = N - i
    s = 0
    for j in range(tmp, N+1, tmp):
        s += ans[j-1]

    if s % 2 != A[tmp - 1]:
        ans[tmp - 1] = 1
        ans_num += 1
        ans_list += str(tmp)
        ans_list += " "


print(ans_num)
print(ans_list[:-1])
### BUGGY CODE ###

import itertools

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

L = []
for i in range(Q):
    L.append(list(map(int, input().split())))

A = []
for m in range(1, M + 1):
    for n in range(N):
        A.append(m)
#print(A)

ans_max = 0
for AA in itertools.combinations(A, N):
    ans = 0
    for ll in L:
        a = ll[0]
        b = ll[1]
        c = ll[2]
        d = ll[3]
        Ab = AA[b-1]
        Aa = AA[a-1]
        s = Ab - Aa
        if (s == c):
            ans += d
    if (ans_max < ans):
        ans_max = ans
print(ans_max)

### FIXED CODE ###

N, M, Q = map(int, input().split())
zz = [list(map(int, input().split())) for _ in range(Q)]

def f(s):
    if len(s) == N:
        return [s]
    result = []
    if s == '':
        r = 0
    else:
        r = int(s[-1])
    for i in range(r, M):
        result.extend(f(s + str(i)))
    return result

ans = 0
V = f('')
for s in V:
    A = [int(c) + 1 for c in s]
    t = 0
    for a, b, c, d in zz:
        if A[b - 1] - A[a - 1] == c:
            t += d
    ans = max(ans, t)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
cnt = 0
while 1:
    jud = 0
    for i in range(n):
        if a[i] % 2 == 1:
            jud += 1
    if jud == n:
        break
    a.sort()
    flag = 0
    for i in range(n):
        if a[i] % 2 == 0 and flag == 0:
            a[i] = a[i] // 2
            flag = 1
        else:
            a[i] *= 3
    cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
cnt = 0
i = 0
for i in range(N):
    while a[i] % 2 == 0:
        a[i] /= 2
        cnt += 1
print(cnt)
### BUGGY CODE ###

n,m,k=map(int,input().split())
edge=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    edge[a].append(b)
    edge[b].append(a)

edgeb=[[] for _ in range(n)]

for _ in range(k):
    c,d=map(int,input().split())
    c,d=c-1,d-1
    edgeb[c].append(d)
    edgeb[d].append(c)

from collections import deque






f_can=[]
for start in range(n):
    dist_friends=[-1]*n
    dist_friends[start]=0
    d=[0]*n
    f=deque([start])

    while f:
        v=f.popleft()        

        for e in edge[v]:
            if dist_friends[e]==-1:
                dist_friends[e]=dist_friends[v]+1
                if dist_friends[e]>1:
                    d[e]=1
                f.append(e)
    
    f_can.append(d)


for start in range(n):

    dist_block=[-1]*n
    dist_block[start]=0
    
    b=deque([start])
    while b:
        v=b.popleft()        

        for e in edgeb[v]:
            if dist_block[e]==-1:
                dist_block[e]=dist_block[v]+1
                if f_can[start][e]==1 and dist_block[e]==1:
                    f_can[start][e]=0

                b.append(e)


ans=[]
for i in f_can:
    ans.append(sum(i))

print(*ans)

### FIXED CODE ###

n,m,k=map(int,input().split())
edge=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    edge[a].append(b)
    edge[b].append(a)

from collections import deque
label=[-1]*n

i=0
for start in range(n):
    if label[start]!=-1:
        continue
    else:
        i+=1
        label[start]=i    
    f=deque([start])
    while f:
        v=f.popleft()        
        for e in edge[v]:
            if label[e]==-1:
                label[e]=i
                f.append(e)   

Renketsu=[0]*(n+1)

for i in label:
    Renketsu[i]+=1

Block=[0]*n
for _ in range(k):
    c,d=map(int,input().split())
    c,d=c-1,d-1
    if label[c]==label[d]:
        Block[c]+=1
        Block[d]+=1

ans=[]
for k in range(n):
    ans.append(Renketsu[label[k]]-1 - len(edge[k]) - Block[k])
print(*ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
b=[10**6]*n
for i in range(n):
    b[i]=a[i]
    if min(b)==a[i]:
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
k=a[0]
for i in range(n):
    if a[i]<=k:
        ans+=1
        k=a[i]
print(ans)
### BUGGY CODE ###

n=int(input())
li = list(map(int,input().split()))
count=1
li2=[]
if(len(li)!=1):
    for i in range(1,n):
        if(i==1):
            if(li[0]>=li[1]):
                count+=1
            continue
       # print(i)
        li2=li[0:i]
        if(min(li2)>=li[i]):
            count+=1
        #print(li2,count)
print(count)


### FIXED CODE ###

n=int(input())
li = list(map(int,input().split()))
count=1
m=n
for i in range(1,n):
    m=min(m,li[i-1])
    if(m==1):
        break
    if(m>=li[i]):
        count+=1
print(count)
### BUGGY CODE ###

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

root1 = []
for i in range(n):
    root1_ = [0] * n
    root1.append(root1_)
root2 = []
for i in range(n):
    root2_ = [0] * n
    root2.append(root2_)
    
for i in range(m):
    root = list(map(int, input().split()))
    root1[root[0] - 1][root[1] - 1] = root[2]
    root1[root[1] - 1][root[0] - 1] = root[2]
    root2[root[0] - 1][root[1] - 1] = root[3]
    root2[root[1] - 1][root[0] - 1] = root[3]

def min_cost(start, end, root):
    confirmed = [[start, 0]]
    edge = [start]
    while len(confirmed) < n:
        candidate = []
        for i in range(len(edge)):
            for j in range(n):
                if root[edge[i] - 1][j] != 0:
                    for k in range(len(confirmed)):
                        if confirmed[k][0] == edge[i]:
                            candidate.append([j + 1, confirmed[k][1] + root[edge[i] - 1][j]])
                            break
        candidate.sort(key = lambda x: x[1])
        for i in range(len(candidate)):
            if candidate[i][0] in [confirmed[i][0] for i in range(len(confirmed))]:
                continue
            else:
                confirmed.append(candidate[i])
                break
        for i in range(len(confirmed)):
            edge.append(confirmed[i][0])
        exclude = []
        for i in range(len(edge)):
            flag = True
            for j in range(n):                
                if root[edge[i] - 1][j] != 0 and (j + 1) not in edge:
                    flag = False
                    break
            if flag == True:
                exclude.append(edge[i])
        edge = list(set(edge) - set(exclude))
    for i in range(len(confirmed)):
        if confirmed[i][0] == end:
            return confirmed[i][1]

cost = []
for i in range(n):
    cost1 = min_cost(s, i + 1, root1)
    cost2 = min_cost(i + 1, t, root2)
    cost.append(cost1 + cost2)
for i in range(n):
    new_cost = cost[i:]
    print(10 ** 15 - min(new_cost))

### FIXED CODE ###

import heapq

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

root1 = []
for i in range(n):
    root1.append({})
root2 = []
for i in range(n):
    root2.append({})
   
for i in range(m):
    u, v, a, b = map(int, input().split())
    root1[u - 1][v] = a
    root1[v - 1][u] = a
    root2[u - 1][v] = b
    root2[v - 1][u] = b

def min_cost(root, start): # 経路の端点を１つ指定して任意の点への最小コストを計算
    S = [[0, start]]
    heapq.heapify(S)
    D = [float("inf")] * n
    D[start - 1] = 0
    while len(S) > 0:
        cost, site = heapq.heappop(S)
        if D[site - 1] < cost:
            continue
        for site2, cost2 in root[site - 1].items():
            if D[site2 - 1] > cost + cost2:
                D[site2 - 1] = cost + cost2
                heapq.heappush(S, [cost + cost2, site2])
    return D

jpy = min_cost(root1, s) # 円で両替地点まで移動する最小コスト
snuke = min_cost(root2, t) # 両替地点からスヌークで移動する最小コスト
cost = [jpy[i] + snuke[i] for i in range(n)] # 両替地点についてループ

minimum_cost = []
temp_min = cost[n - 1]
for i in reversed(range(n)):
    temp_min = min(temp_min, cost[i])
    minimum_cost.append(temp_min)

for i in reversed(range(n)):
    print(10 ** 15 - minimum_cost[i])
### BUGGY CODE ###

s = list(input())
q = int(input())

reverse = False
count = 0
for i in range(q):
    qu = input()
    if qu[0] == "1":
        count += 1
        if reverse:
            reverse = False
        else:
            reverse = True
    else:
        _, f, c = qu.split()
        if reverse:
            if f == "1":
                s = s + [c]
            else:
                s = [c] + s
        else:
            if f == "1":
                s = [c] + s
            else:
                s = s + [c]

if count % 2:
    s = s[::-1]

print("".join(s))

### FIXED CODE ###

from collections import deque

s = input()
q = int(input())

reverse = False
count = 0
mae = deque()
ushiro = deque()
for i in range(q):
    qu = input()
    if qu[0] == "1":
        count += 1
        if reverse:
            reverse = False
        else:
            reverse = True
    else:
        _, f, c = qu.split()
        if reverse:
            if f == "1":
                ushiro.append(c)
            else:
                mae.appendleft(c)
        else:
            if f == "1":
                mae.appendleft(c)
            else:
                ushiro.append(c)

s = "".join(mae) + s + "".join(ushiro)

if count % 2:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

T=int(input())
 
Query=[]
for i in range(T):
  Query.append(list(map(int,input().split())))
 
for i in range(T):
  appear=[]
  appear.append(Query[i][0])
  while(True):
    if Query[i][0]%Query[i][1]>Query[i][2] or Query[i][0]<Query[i][1]:
      print('No')
      break;
    Query[i][0]=Query[i][0]%Query[i][1] #昼
    if Query[i][0] in appear:
      print('Yes')
      break;
    else:
      appear.append(Query[i][0])
    if Query[i][0]<=Query[i][2]: #夜
      Query[i][0]+=Query[i][3]

### FIXED CODE ###

def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
T=int(input())
 
Query=[]
for i in range(T):
  Query.append(list(map(int,input().split())))
 
for i in range(T):
  while(True):
    if Query[i][0]%Query[i][1]>Query[i][2] or Query[i][0]<Query[i][1] or Query[i][1]>Query[i][3]:
      print('No')
      break;
    G=gcd(Query[i][1],Query[i][3]) #この倍数分の増減のみ考えれば良い
    '''
    A,B,C,DがQuery[i]の0,1,2,3に対応
    BmodG,DmodGは0(GはB,Dの約数であるため)よりmodGの世界で個数の増減はない。昼の購入で0個減少。夜の仕入れで0個増加。
    つまり、初期個数をAmodGとすると、個数は一定
    出現する可能性のあるBは買う個数であり、B-Gを考えると、買いきれない個数で出現しうる最大の個数が求まる。
    但し、初期個数を考える必要がある。
    初期個数によってループする幅が一緒でも取りうる値は異なる。
    
    例：
    B=24,C=19,D=36 この時,G=12
    
    A=31の場合 AmodG(本来の個数)
    7(31)→7(7)→7(43)→7(19)→7(31)→...
    A=30の場合 AmodG(本来の個数)
    6(30)→6(6)→6(42)→6(18)→6(30)→...
    
    Bを超えない最大数について、初期個数を考慮すると、B-G+AmodGとなる。
    G>AmodGであるため、この数が購入数Bを超えることはない
    つまり、B-G+AmodG>CならばNo,そうでなければYes
    '''
    if Query[i][1]-G+Query[i][0]%G>Query[i][2]:
      print('No')
      break;
    else:
      print('Yes')
      break;
### BUGGY CODE ###

from itertools import combinations


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

ans = 0
for a, b, c in combinations(L, 3):
    if c < a + b:
        ans += 1

print(ans)


### FIXED CODE ###

from bisect import bisect_left, bisect_right

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

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        ans += bisect_left(L, L[i] + L[j]) - j - 1

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

n, w = map(int, input().split())
weight = []
value = []
for _ in range(n):
    wi, vi = map(int, input().split())
    weight.append(wi)
    value.append(vi)
weight.append(0)
value.append(0)
dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(w + 1):
        if j - weight[i] >= 0:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - weight[i]] + value[i])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(dp[n][w])

### FIXED CODE ###

n, w = map(int, input().split())
weight = []
value = []
for _ in range(n):
    wi, vi = map(int, input().split())
    weight.append(wi)
    value.append(vi)
weight.append(0)
value.append(0)
dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(w + 1):
        if j - weight[i] >= 0:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - weight[i]] + value[i])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(dp[n][w])
### BUGGY CODE ###

import sys


def Sieve(N, AList):
    AList.sort()
    N_NotDivisible = 0
    while( len(AList) > 0 ):
        if(len(AList) > 1):
            if(AList[0]!= AList[1]):
                N_NotDivisible+= 1
                value = AList[0]
                AList = [ i for i in AList if i % value != 0 ]
            else:
                index = 2
                while(index < len(AList) and AList[index-1] == AList[index]):
                    index += 1
                for i in range(index):
                    AList.pop(0)

        else:
            N_NotDivisible+= 1
            break
    #print(Mins)
    return N_NotDivisible

if(__name__ == "__main__"):

    N = int( input().strip() )
    AList_str = input().strip().split()

    AList = [0] * N
    for i in range(N):
        AList[i] = int(AList_str[i])
    N_NotDivisible= Sieve(N, AList)
    print(N_NotDivisible)


### FIXED CODE ###

import sys

def Sieve2(N, AList, Bools, Max_A):
    N_NotDivisible = 0
    value = 0
    for i in range(N):
        if(AList[i]>value):
            value = AList[i]
            if(Bools[value]==True):
                N_NotDivisible += 1

            for j in range(2, Max_A//value+1, 1 ):
                Bools[j*value] = False
    #print(Mins)
    return N_NotDivisible


if(__name__ == "__main__"):

    N = int( input().strip() )
    AList_str = input().strip().split()
    Max = 0
    AList = [0] * N
    for i in range(N):
        AList[i] = int(AList_str[i])
        Max = max(AList[i], Max)
    Bools = [False] * (Max+1)
    AList.sort()
    Dups = []
    for Num in range(N):
        value = AList[Num]
        Bools[value] = True
        if(Num < N-1 and AList[Num] == AList[Num+1]):
            Dups.append(value)
    for Num in range(len(Dups)):
        value = Dups[Num]
        Bools[value] = False


    N_NotDivisible= Sieve2(N, AList, Bools, Max)
    print(N_NotDivisible)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
MOD = 1000000007
ans = 0

for i in range(N):
  x = sum(A[i+1:]) % MOD
  y = (A[i] * x) % MOD
  ans += y
  ans %= MOD

print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
MOD = 1000000007
x = sum(A)
ans = 0
 
for i in range(N):
  x -= A[i]
  y = x % MOD
  z = (A[i] * y) % MOD
  ans += z
  ans %= MOD

print(ans)