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

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

from collections import deque
import copy

class Puzzle(list):
    def __init__(self, size):
        list.__init__(self)
        self.size = size
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle(N2)
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    def isTarget(p):
        for i in range(N2):
            if p[i] != i+1:
                return False
        return True

    def bfs(s):
        cnt = 0
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            cnt += 1
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if tx < 0 or ty < 0 or tx >= N or ty >= N:
                    continue
                v = copy.deepcopy(u)
                v[u.space], v[tx * N + ty] = v[tx * N + ty], v[u.space]
                v.space = tx * N + ty
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print(len(ans))





### FIXED CODE ###

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

from collections import deque
import copy

class Puzzle(list):
    def __init__(self):
        list.__init__(self)
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self[:]))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle()
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    target = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    def isTarget(p):
        return p[:] == target[:]

    def bfs(s):
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if not (0<= tx < N and 0 <= ty < N):
                    continue
                v = Puzzle()
                v[:] = u[:]
                v.path = u.path
                change = tx * N + ty
                v[u.space], v[change] = v[change], v[u.space]
                v.space = change
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print(len(ans))
### BUGGY CODE ###

def main():
    n, q = map(int, input().split())
    s = input()
    lr =  [list(map(int, input().split())) for _ in range(q)]
    
    t = [0] * n
    pre = s[0]
    for i in range(1, n):
        if pre == 'A' and s[i] == 'C':
            t[i] = 1
        pre = s[i]
    for l, r in lr:
        print(sum(t[l:r]))
        
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, q = map(int, input().split())
    s = input()
    
    t = [0] * n
    pre = s[0]
    t_sum = 0
    for i in range(1, n):
        if pre == 'A' and s[i] == 'C':
            t[i] = t_sum + 1
            t_sum +=  1
        else: 
            t[i] = t_sum
        pre = s[i]
    for _ in range(q):
        l, r = map(int, input().split())
        print(t[r - 1] - t[l - 1])
        
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]


N, M = [int(x) for x in input().split()]
S = [int(x) for x in input().split()]
T = [int(x) for x in input().split()]

DP = [[0] * (M + 1) for _ in range(N + 1)]
DP[0] = [1] * (M + 1)
for n in range(1, N + 1):
    DP[n][0] = DP[n - 1][0]
    for m in range(1, M + 1):
        DP[n][m] = DP[n][m - 1] + DP[n - 1][m] - DP[n - 1][m - 1]
        if S[n - 1] == T[m - 1]:
            DP[n][m] += DP[n - 1][m - 1]

print(DP[n][m] % MOD)


### FIXED CODE ###

import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

def main():
    """"ここに今までのコード"""
    N, M = [int(x) for x in input().split()]
    S = [int(x) for x in input().split()]
    T = [int(x) for x in input().split()]

    DP = [[0] * (M + 1) for _ in range(N + 1)]
    DP[0] = [1] * (M + 1)
    for n in range(1, N + 1):
        DP[n][0] = DP[n - 1][0]
        for m in range(1, M + 1):
            DP[n][m] = DP[n][m - 1] + DP[n - 1][m] - DP[n - 1][m - 1]
            DP[n][m] %= MOD
            if S[n - 1] == T[m - 1]:
                DP[n][m] += DP[n - 1][m - 1]
                DP[n][m] %= MOD
    print(DP[n][m])


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

S = input()
N = len(S)
for i in range(N):
    if S[i] == 'A':
        a_index = i
        break
for i in range(N):
    if S[::-1][i] == 'Z':
        z_index = i
        break

print(N - z_index - a_index)


### FIXED CODE ###

S = input()
N = len(S)
for i, s in enumerate(S):
    if s == 'A':
        a_index = i
        break
for i, s in enumerate(S[::-1]):
    if s == 'Z':
        z_index = i
        break

print(N - z_index - a_index)
### BUGGY CODE ###

import math
def gcd(a, b, c):
    x = math.gcd(a, b)
    return(math.gcd(x, c))

K = int(input())
sum = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            sum += gcd(i + 1, j + 1, k + 1)
print(sum)


### FIXED CODE ###

import math
def gcd(a, b, c):
    x = math.gcd(a, b)
    return(math.gcd(x, c))
K = int(input())
sum = 0
for i in range(1, K + 1):
    for j in range(i, K + 1):
        for k in range(j, K + 1):
            if i == j == k:
                sum += gcd(i, j, k)
            elif i == j or j == k or k == i:
                sum += 3 * gcd(i, j, k)
            else:
                sum += 6 * gcd(i, j, k)
print(sum)
### BUGGY CODE ###

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    b = list(map(int, input().split()))
  else:
    # b = [1,2,1]
    # b = [2,2]
    b = [1,1,1,2,2,1,2,3,2]
    N = len(b)

  if check(b) != True:
    print(-1)
    
def check(B):
  # if 'get_ipython' in globals(): print(B)
  lenB = len(B)
  if lenB == 0 :
    return True
  for i in range(lenB):
    if B[i] == i+1:
      if check(B[:i]+B[(i+1):]) == True:
        print(B[i])
        return True
        break
    
main()

### FIXED CODE ###

import sys

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    b = [int(i) for i in input().split()] 
  else:
    # b = [1,2,1]
    # b = [2,2]
    b = [1,1,1,2,2,1,2,3,2]
    N = len(b)

  ans = []
  while True:
    for i in range(N-1,-1,-1):
      if b[i] == i+1:
        ans.append(i+1)
        del b[i]
        N = N -1
        break
      if i == 0:
        print(-1)
        sys.exit()
    if N == 0:
      break

  for i in reversed(ans):
    print(i)
    
main()
### BUGGY CODE ###

N,M=map(int,input().split())
cake=[list(map(int,input().split()))for _ in[0]*N]
dp=[[[0]*3]for _ in[0]*(M+1)]
for c in cake:
    for i in range(M-1,-1,-1):
        for t in dp[i]:
            dp[i+1]+=[[c[i]+t[i]for i in range(3)]]
        if len(dp[i])>10:
            a=[sum(t)for t in dp[i]]
            Max,Min=max(a),min(a)
            for s,t,u in dp[i]:
                if s>0 and t>0 and u>0 and s+t+u<Max:dp[i].remove([s,t,u])
                if s<0 and t<0 and u<0 and s+t+u>Min:dp[i].remove([s,t,u])
print(max(sum(map(abs,x))for x in dp[M]))

### FIXED CODE ###

N,M=map(int,input().split())
sums=[[]for _ in[0]*8]
for _ in[0]*N:
    c=list(map(int,input().split()))
    for t in range(8):
        sums[t]+=[sum(c[i]*[-1,1][t&(1<<i)>0]for i in range(3))]
if M:print(max(sum(sorted(sums[i])[-M:])for i in range(8)))
else:print(0)
### BUGGY CODE ###

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

    dp = [-1] * (W + 1)
    dp[0] = 0

    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] == -1: continue
            dp[i + w] = max(dp[i + w], dp[i] + v)

    print(max(dp))

main()


### FIXED CODE ###

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

    dp = [-1] * (W + 1)
    dp[0] = 0

    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] != -1 and dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v

    print(max(dp))

main()
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[13]:


S = list(input())


# In[14]:


ans = 0
for i in range(S.count("W")):
    ans += S.index("W")-i
    S[S.index("W")] = "B"
print(ans)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[30]:


S = list(input())


# In[31]:


w_count = S.count("W")
print(sum([idx for idx,x in enumerate(S) if x == "W"]) - (w_count-1)*w_count//2)


# In[ ]:
### BUGGY CODE ###

stdin =open(0).read().split('\n')
N=int(stdin[0])
A=list(map(int,stdin[1].split()))
d=dict(zip(set(A), [0]*len(set(A))))
ans=0
for i in set(A):
    d[i]=A.count(i)
    ans+=d[i]*(d[i]-1)//2
for a in A:
    num = d[a]
    print(ans-num*(num-1)//2+(num-1)*(num-2)//2)

### FIXED CODE ###

stdin =open(0).read().split('\n')
N=int(stdin[0])
A=list(map(int,stdin[1].split()))
from collections import Counter
C=Counter(A)
ans=0
for i in C.values():
    ans+=i*(i-1)//2
for a in A:
    num = C[a]
    print(ans-num*(num-1)//2+(num-1)*(num-2)//2)
### BUGGY CODE ###

arr = []

for i in range(int(input())):
  command_line = input().split(" ")
  command = command_line[0]
  arg = ""
  if len(command_line) > 1: arg = command_line[1]

  if command == "insert":
    arr.insert(0, arg)
  if command == "delete":
    if arg in arr: arr.remove(arg)
  if command == "deleteFirst":
    del arr[0]
  if command == "deleteLast":
    del arr[-1]

print(" ".join(arr))

### FIXED CODE ###

from collections import deque

q = deque()

for i in range(int(input())):
  command_line = input().split(" ")
  command = command_line[0]
  arg = ""
  if len(command_line) > 1: arg = command_line[1]

  if command == "insert":
    q.appendleft(arg)
  elif command == "delete":
    try:
      q.remove(arg)
    except ValueError:
      pass
  elif command == "deleteFirst":
    q.popleft()
  else:
    q.pop()

print(" ".join(q))
### BUGGY CODE ###

N,M=map(int,input().split())
L=[]
R=[]
for i in range(M):
  l,r=map(int,input().split())
  L.append(l)
  R.append(r)
count=0
for i in range(1,N+1):
  for j in range(M):
    if L[j]>i or i>R[j]:
      break
  else:
    count+=1
print(count)

### FIXED CODE ###

N,M=map(int,input().split())
L=[]
R=[]
for i in range(M):
  l,r=map(int,input().split())
  L.append(l)
  R.append(r)
count=0
if max(L)>min(R):
  print(0)
else:
  print(min(R)-max(L)+1)
### BUGGY CODE ###

N, X, Y = map(int, input().split())

dp = [[N+10] * N for i in range(N)]
for i in range(N-1):
    dp[i][i+1] = 1
for i in range(1, N):
    dp[i][i-1] = 1
dp[X-1][Y-1] = 1
dp[Y-1][X-1] = 1
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

mindcnt = {}
for i in range(N):
    mindcnt[i] = 0

for i in range(N):
    for j in range(i+1, N):
        mind = dp[i][j]
        mindcnt[mind] += 1

for k in range(1, N):
    print(mindcnt[k])


### FIXED CODE ###

N, X, Y = map(int, input().split())

mind = [[N] * N for i in range(N)]
    
for i in range(N):
    for j in range(i+1, N):
        mind[i][j] = min(abs(j-i), abs((X-1)-i)+1+abs(j-(Y-1)), abs((Y-1)-i)+1+abs(j-(X-1)))

mindcnt = [0] * N
for i in range(N):
    for j in range(i+1, N):
        d = mind[i][j]
        mindcnt[d] += 1

for k in range(1, N):
    print(mindcnt[k])
### BUGGY CODE ###

s = input()
dp = [0 for _ in range(13)]
dp[0] = 1
c = 1000000007
m = 1
r13 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
r10 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
for i in range(len(s) - 1, -1, -1):
    ndp = [0 for _ in r13]
    if s[i] == "?":
        for j in r10:
            jm = j * m
            for k in r13:
                index = (jm + k) % 13
                ndp[index] = (ndp[index] + dp[k]) % c
    else:
        jm = int(s[i]) * m
        for k in r13:
            index = (jm + k) % 13
            ndp[index] = (ndp[index] + dp[k]) % c
    dp = ndp[:]
    m = m * 10 % 13
print(dp[5])

### FIXED CODE ###

s = input()
dp = [0 for _ in range(13)]
dp[0] = 1
c = 1000000007
m = 1
r13 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
r10 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
for i in range(len(s) - 1, -1, -1):
    ndp = [0 for _ in r13]
    if s[i] == "?":
        for j in r10:
            jm = j * m
            for k in r13:
                index = (jm + k) % 13
                ndp[index] = (ndp[index] + dp[k]) % c
    else:
        jm = int(s[i]) * m
        for k in r13:
            index = (jm + k) % 13
            ndp[index] = (ndp[index] + dp[k]) % c
    dp = ndp[:]
    m = m * 10 % 13
print(dp[5])
### BUGGY CODE ###


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


ans = 1


for i in range(2,int(p**(1./n))+1):
	while(p%(i**n)==0):
		ans*=i
		p//=i**n
print(ans)

### FIXED CODE ###

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


ans = 1
if(n==1):print(p)
else:

	for i in range(2,int(p**(1./n))+1):
		while(p%(i**n)==0):
			ans*=i
			p//=i**n
	print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
L = list(set(a))
res = 0

for i in L:
    X = a.count(i)
    if X < i:
        res += X
    
    else:
        res += X - i

print(res)

### FIXED CODE ###

from collections import Counter
N = int(input())
a = list(map(int, input().split()))
L = list(set(a))
res = 0
d = Counter()
d.update(a)
for i in L:
    X = d[i]
    if X < i:
        res += X
    
    else:
        res += X - i

print(res)
### BUGGY CODE ###

import math
 
def comb(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
 
N = int(input())
s = ["".join(sorted(input())) for _ in range(N)]
 
 
unique_s = set(s)
 
output = 0
for k in unique_s:
     if s.count(k) != 1:
        output += int(comb(s.count(k), 2))
 
print(output)

### FIXED CODE ###

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

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

output = 0
dic = dict()
for i in range(N):
    tmp = ''.join(sorted(s[i]))
    if tmp not in dic:
        dic[tmp] = 1
    else:
        output += dic[tmp]
        dic[tmp] += 1

print(output)
### BUGGY CODE ###

K,S=[int(i) for i in input().split()]
s=0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z==S:
                s+=1
print(s)

### FIXED CODE ###

K,S=[int(i) for i in input().split()]
s=0
for x in range(K+1):
    for y in range(K+1):
        z=S-x-y
        if 0<=z and z<=K:
            s+=1
print(s)
### BUGGY CODE ###

import itertools
n,k=map(int,input().split())
price=list(map(int,input().split()))

n_list=[]
for com in itertools.combinations(price,k):
    s=sum(com)
    n_list.append(s)
print(min(n_list))


### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
print(sum(sorted(p)[:K]))
### BUGGY CODE ###

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

ans = 0
for i in range(N):
    ans ^= A[i]

for i in range(N):
    A[i] = (~ans)&A[i]

A = [a for a in A if a != 0]
b = []

while A:
    M = max(A)
    for i in range(len(A)-1,-1,-1):
        if len(bin(M))==len(bin(A[i])):
            A[i] ^= M
        else:
            break
    A = sorted([a for a in A if a != 0])
    b.append(M)    

b = b[::-1]
ans_ = 0
for i in range(len(b)):
    M = b[i]
    for j in range(i+1,len(b)):
        m = b[j]
        if len(bin(M))==len(bin(M&m)):
            b[j] ^= M
    ans_ ^= M

ans += ans_*2
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
for a in A:
    ans ^= a
M = 2**60-1
b = M^ans
for i in range(N):
    A[i] &= b
A.sort(reverse=True)
for i in range(min(60,N)):
    a = A[i]
    if a == 0:
        break
    l = len(bin(a))-3
    for j in range(N):
        if j==i:
            continue
        if A[j]//2**l%2==1:
            A[j] ^= a
        else:
            if i < j:
                break
    A.sort(reverse=True)
s = 0
for a in A:
    s ^= a
ans += 2*s
print(ans)
### BUGGY CODE ###

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

ans = 1
for i in A:
    ans *= i
if ans > 1000000000000000000:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

ans = 1
if 0 in A:
    print(0)
else:
    for i in A:
        ans *= i
        if ans > 1000000000000000000:
            print(-1)
            exit()
    print(ans)
### BUGGY CODE ###

import os
import sys
from collections import defaultdict
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

import time

st = time.time()

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# グラフつくる
nodes = set()
graph = defaultdict(list)
ins = defaultdict(int)
sources = []
for i in range(N):
    for j in range(N - 2):
        a, b = i, A[i][j] - 1
        a, b = min(a, b), max(a, b)
        c, d = i, A[i][j + 1] - 1
        c, d = min(c, d), max(c, d)

        graph[a * N + b].append(c * N + d)
        ins[c * N + d] += 1
        sources.append(a * N + b)

        nodes.add(a * N + b)
        nodes.add(c * N + d)

# トポロジカルソート
S = []
for v in nodes:
    if ins[v] == 0:
        S.append(v)
L = []
while S:
    if time.time() - st >= 1.98:
        print(-1)
        exit()

    v = S.pop()
    L.append(v)
    for u in graph[v]:
        ins[u] -= 1
        if ins[u] == 0:
            S.append(u)

if len(L) != len(nodes):
    print(-1)
    exit()

seen = []


@lru_cache(maxsize=None)
def dfs(v):
    if time.time() - st >= 1.98:
        print(-1)
        exit()

    ret = 0
    for u in graph[v]:
        ret = max(ret, dfs(u))
    return ret + 1


ans = 0
for v in sources:
    ans = max(ans, dfs(v))
print(ans)


### FIXED CODE ###

import os
import sys
from collections import defaultdict, deque
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

graph = [[] for _ in range(N ** 2)]
ins = [0] * (N ** 2)
for i in range(N):
    for j in range(N - 2):
        a, b = i, A[i][j] - 1
        c, d = i, A[i][j + 1] - 1

        if a > b:
            a, b = b, a
        if c > d:
            c, d = d, c

        graph[a * N + b].append(c * N + d)
        ins[c * N + d] += 1

zeros = []
seen = []
for v, cnt in enumerate(ins):
    if cnt == 0:
        zeros.append(v)
        seen.append(v)

ans = 0
while zeros:
    nz = []
    for v in zeros:
        for u in graph[v]:
            ins[u] -= 1
            if ins[u] == 0:
                nz.append(u)
                seen.append(u)
    zeros = nz
    ans += 1
if len(seen) == len(graph):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import sys
from collections import deque
H, W = map(int, input().split())
gridgraph = []
for line in sys.stdin.readlines():
    line = line.rstrip()
    gridgraph.append(list(line))
q = deque()
visited = [[False]*W for _ in range(H)]
ans = [[1e+9]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == "#":
            q.append((i, j))
            visited[i][j] = True
            ans[i][j] = 0

while len(q):
    cy, cx = q.popleft()

    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if not (cy+dy >= 0 and H-1 >= cy+dy and cx+dx >= 0 and W-1 >= cx+dx):
            continue
        if visited[cy+dy][cx+dx]:
            continue
        visited[cy+dy][cx+dx] = True
        ans[cy+dy][cx+dx] = min(ans[cy+dy][cx+dx], ans[cy][cx]+1)
        q.append((cy+dy, cx+dx))

min_value = 0
for a in ans:
    min_value = max(min_value, max(a))
print(min_value)


### FIXED CODE ###

import sys
from collections import deque
H, W = map(int, input().split())
gridgraph = []
for line in sys.stdin.readlines():
    line = line.rstrip()
    gridgraph.append(list(line))
q = deque()
visited = [[False]*W for _ in range(H)]
ans = [[1e+9]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == "#":
            q.append((i, j))
            visited[i][j] = True
            ans[i][j] = 0

while len(q):
    cy, cx = q.popleft()

    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if not (cy+dy >= 0 and H-1 >= cy+dy and cx+dx >= 0 and W-1 >= cx+dx):
            continue
        if visited[cy+dy][cx+dx]:
            continue
        visited[cy+dy][cx+dx] = True
        ans[cy+dy][cx+dx] = min(ans[cy+dy][cx+dx], ans[cy][cx]+1)
        q.append((cy+dy, cx+dx))

min_value = 0
for a in ans:
    min_value = max(min_value, max(a))
print(min_value)
### BUGGY CODE ###

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

for i in range(1, N):
  dt, da = map(int, input().split())
  t, a = dt, da
  
  while t < T[i-1] or a < A[i-1]:
    t += dt
    a += da
  
  T[i], A[i] = t, a
  
print(A[-1] + T[-1])

### FIXED CODE ###

import math

N = int(input())
A, T = [0 for i in range(N)], [0 for i in range(N)]
T[0], A[0] = map(int, input().split())

for i in range(1, N):
  dt, da = map(int, input().split())
  for j in range(max(A[i-1]//da, T[i-1]//dt)-1, max(A[i-1]//da, T[i-1]//dt)+3):
    if A[i-1] <= j * da and T[i-1] <= j * dt:
      n = j
      break
      
  T[i], A[i] = dt * n, da * n

print(A[N-1] + T[N-1])
### BUGGY CODE ###

N, M = map(int, input().split())
A=[]
MOD=1000000007
for _ in range(M):
    a = int(input())
    A.append(a)

C = [0]*(N+1)
C[0]=1
#print(C)
for i in range(N):
    if i+1 not in A:
        C[i+1]+=C[i]%MOD
    if i+2 not in A and i<N-1:
        C[i+2]+=C[i]%MOD
    #print(C)
print(C[N]%MOD)


### FIXED CODE ###

N, M = map(int, input().split())
D=[1]*(N+1)
MOD=1000000007
for _ in range(M):
    i = int(input())
    D[i]=0

C = [0]*(N+1)
C[0]=1
for i in range(N-1):
    C[i+1]+=(C[i]*D[i])%MOD
    C[i+2]+=(C[i]*D[i])%MOD
C[N]+=(C[N-1]*D[N-1])%MOD
    #print(C)
print(C[N]%MOD)
### BUGGY CODE ###

import itertools
N = int(input())
A = list(map(int, input().split()))
ans = 0

for i in range(N-1):
  wa = i + A[i]
  for j in range(i+1,N):
    sa = j - A[j]
    if wa == sa:
      ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
D = {}

for j in range(N):
  if j-A[j] in D:
    ans += D[j-A[j]]
  if j+A[j] in D:
    D[j+A[j]] += 1
  else:
    D[j+A[j]] = 1
    
print(ans)
### BUGGY CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    for i in range(N):
        for j in range(i):
            ans += A[i]*A[j]
            if ans > 10**9+7:
                ans %= (10**9+7)
    print(ans)
resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    S = sum(A)
    count = S
    ans = 0
    for i in A:
        count -= i
        ans += count*i
        if ans > 10**9+7:
            ans %= (10**9+7)
    print(ans)
resolve()