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

from collections import deque
from collections import defaultdict

def main():
    N, K, L = (int(_) for _ in input().split())
    road = defaultdict(list)
    train = defaultdict(list)
    for i in range(K):
        p, q = (int(_) for _ in input().split())
        road[p].append(q)
        road[q].append(p)
    for i in range(L):
        p, q = (int(_) for _ in input().split())
        train[p].append(q)
        train[q].append(p)
    visited_r = [0] * (N+1)
    gn = 1
    for p in range(1, N+1):
        if visited_r[p] != 0:
            continue
        d = deque()
        d.append(p)
        while d:
            q = d.popleft()
            visited_r[q] = gn
            if q in road:
                for r in road[q]:
                    if visited_r[r] == 0:
                        d.append(r)
        gn += 1
    visited_t = [0] * (N+1)
    gn = 1
    for p in range(1, N+1):
        if visited_t[p] != 0:
            continue
        d = deque()
        d.append(p)
        while d:
            q = d.popleft()
            visited_t[q] = gn
            if q in train:
                for r in train[q]:
                    if visited_t[r] == 0:
                        d.append(r)
        gn += 1
    dict = defaultdict(int)
    for i in range(1, N+1):
        dict[(visited_r[i], visited_t[i])] += 1
    for i in range(1, N+1):
        print(dict[(visited_r[i], visited_t[i])], end=' ')
    print('')
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

#Union-Find木の構築
import sys
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

    def buildTree(a):
        #aT = [0]*(iN+1)
        aT = list(range(iN+1))
        for p,q in a:
            rp = getRoot(aT,p)
            rq = getRoot(aT,q)
            thisRoot = max(rp,rq,q) #みんな小さい方に合わせてるのでデカい方に合>わせてみる
            aT[p] = thisRoot
            aT[q] = thisRoot
            aT[rp] = thisRoot #これで Union してるつもり
            aT[rq] = thisRoot
        return aT
    def getRoot(a,i): #find
        #if a[i] == i or a[i] == 0:
        #   if a[i] == 0 : a[i] = i
        if a[i] == i :
            return i
    #   elif i < a[i] :
        else :
            a[i] = getRoot(a,a[i])
            return a[i]
    #   else:
    #       print("! ",i,a[i])

    aT道 = buildTree(aD[0:iK])
    aT鉄道 = buildTree(aD[iK:])
    aRet = []
    dRet = {}
    for i in range(1,iN+1):
        # いやはやこんなもんもキーになるのか。
        Comb = (getRoot(aT道,i), getRoot(aT鉄道,i))
        aRet.append(Comb)
        if Comb in dRet:
            dRet[Comb] += 1
        else:
            dRet[Comb] = 1
    print(" ".join([str(dRet[_]) for _ in aRet]))

解()
### BUGGY CODE ###

H,W = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
sy,sx = sy-1,sx-1
gy,gx = gy-1,gx-1
S = [input() for i in range(H)]

import heapq
INF = float('inf')
dist = [[INF]*W for i in range(H)]
dist[sy][sx] = 0
hq = [(0,sx,sy)]
heapq.heapify(hq)
while hq:
    d,x,y = heapq.heappop(hq)
    for dx in range(-2,3):
        for dy in range(-2,3):
            if dx == dy == 0: continue
            nx,ny = x+dx,y+dy
            if not 0 <= nx < W: continue
            if not 0 <= ny < H: continue
            if S[ny][nx] == '#': continue
            if abs(dx)+abs(dy) <= 1:
                if dist[ny][nx] <= dist[y][x]: continue
                dist[ny][nx] = dist[y][x]
                heapq.heappush(hq, (d,nx,ny))
            else:
                if dist[ny][nx] <= dist[y][x] + 1: continue
                dist[ny][nx] = dist[y][x] + 1
                heapq.heappush(hq, (d+1, nx,ny))
print(-1 if dist[gy][gx]==INF else dist[gy][gx])

### FIXED CODE ###

H,W = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
sy,sx = sy-1,sx-1
gy,gx = gy-1,gx-1
S = [input() for i in range(H)]

import heapq
INF = float('inf')
dist = [[INF]*W for i in range(H)]
dist[sy][sx] = 0
hq = [(0,sx+sy*W)]
heapq.heapify(hq)
while hq:
    d,v = heapq.heappop(hq)
    y,x = divmod(v,W)
    for dx in range(-2,3):
        for dy in range(-2,3):
            if dx == dy == 0: continue
            nx,ny = x+dx,y+dy
            if not 0 <= nx < W: continue
            if not 0 <= ny < H: continue
            if S[ny][nx] == '#': continue
            if abs(dx)+abs(dy) <= 1:
                if dist[ny][nx] <= dist[y][x]: continue
                dist[ny][nx] = dist[y][x]
                heapq.heappush(hq, (d,nx+ny*W))
            else:
                if dist[ny][nx] <= dist[y][x] + 1: continue
                dist[ny][nx] = dist[y][x] + 1
                heapq.heappush(hq, (d+1, nx+ny*W))
print(-1 if dist[gy][gx]==INF else dist[gy][gx])
### BUGGY CODE ###

import sys,collections,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,Q = Is()
S = S()
lis = [0]*(N-1)
for i in range(N-1):
    if S[i:i+2] == "AC":
        lis[i] = 1
for q in range(Q):
    l,r = Is()
    print(sum(lis[l-1:r-1]))


### FIXED CODE ###

import sys,collections,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,Q = Is()
S = S()
lis = [0]
t = 0
for i in range(N):
    if S[i:i+2] == "AC":
        t += 1
    lis.append(t)
for q in range(Q):
    l,r = Is()
    print(lis[r-1]-lis[l-1])
### BUGGY CODE ###

from scipy.sparse import csr_matrix, csgraph
n, m, s, t = map(int, input().split())
src = [list(map(int, input().split())) for _ in range(m)]
u, v, a, b = zip(*src)
pa = csgraph.dijkstra(csr_matrix((a, (u, v)), (n + 1, n + 1)), False, s)
pb = csgraph.dijkstra(csr_matrix((b, (u, v)), (n + 1, n + 1)), False, t)

dist = [-1] * (n + 1)
for i in range(1, n + 1):
    dist[i] = int(pa[i] + pb[i])
dist = sorted(enumerate(dist), key=lambda x: x[1], reverse=True)
dist.pop()

snuk = 10 ** 15
for i in range(n):
    while dist[-1][0] <= i:
        dist.pop()
    else:
        print(snuk - dist[-1][1])

### FIXED CODE ###

from heapq import heappop, heappush
n, m, s, t = map(int, input().split())
edge_a = [set() for _ in range(n + 1)]
edge_b = [set() for _ in range(n + 1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    edge_a[u].add((v, a))
    edge_a[v].add((u, a))
    edge_b[u].add((v, b))
    edge_b[v].add((u, b))

def dijkstra(edge, s):
    sp = [10 ** 19] * (n + 1)
    sp[s] = 0
    q = [(0, s)]
    while q:
        dist, s = heappop(q)
        for t, w in edge[s]:
            if dist + w < sp[t]:
                sp[t] = dist + w
                heappush(q, (sp[t], t))
    return sp

sp_a = dijkstra(edge_a, s)
sp_b = dijkstra(edge_b, t)
dist = [int(sp_a[-1] + sp_b[-1])]
for i in range(n - 1, 0, -1):
    dist.append(min(dist[-1], int(sp_a[i] + sp_b[i])))

snuk = 10 ** 15
print(*(snuk - d for d in reversed(dist)), sep='\n')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2000000)

from fractions import gcd
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x


mod = 1000000007


def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y/2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))



n=int(input())
aa=[]
aa=list(map(int,input().split()))
# for i in range(n):
#     aa.append(randint(1,10**6))

bb=lcm(aa)
mod=10**9+7
ans=0
for i in range(n):
    ccc=div(bb,aa[i])
    ans=int((ccc%mod+ans%mod)%mod)
print(int(ans))

### FIXED CODE ###

import sys
sys.setrecursionlimit(2000000)

from fractions import gcd
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x


mod = 1000000007


def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y/2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))



n=int(input())
aa=[]
aa=list(map(int,input().split()))
# for i in range(n):
#     aa.append(randint(1,10**6))

bb=lcm(aa)
mod=10**9+7
ans=0
for i in range(n):
    ccc=div(bb,aa[i])
    ans=int((ccc%mod+ans%mod)%mod)
print(int(ans))
### BUGGY CODE ###

n=int(input())
s=input()
a=n
for i in range(n):
  a=min(a,s[:i].count('W')+s[i+1:].count('E'))
print(a)

### FIXED CODE ###

n=int(input())
s=input()
t=s[1:].count('E')
a=t
for i in range(n-1):
  t+=(s[i]=='W')-(s[i+1]=='E')
  a=min(a,t)
print(a)
### BUGGY CODE ###

N = int(input())
mat = []
for i in range(N):
    mat.append(list(map(lambda x:int(x)-1, input().split())))

ind = [0 for i in range(N)]
days = 0
while True:
    madeMatch = False
    
    played = [False for i in range(N)]
    for i in range(N):
        if ind[i] == N-1 or played[i]: continue
        playAgainst = mat[i][ind[i]]
        if mat[playAgainst][ind[playAgainst]] == i and not played[playAgainst]:
            madeMatch = True
            played[i] = True
            played[playAgainst] = True

            ind[playAgainst] += 1
            ind[i] += 1
    if not madeMatch: break
    days += 1
    
if all(x == N-1 for x in ind):
    print(days)
else:
    print(-1)


### FIXED CODE ###

import time

t0 = time.clock()

N = int(input())
mat = []
for i in range(N):
    mat.append(list(map(lambda x:int(x)-1, input().split())))

ind = [0 for i in range(N)]
days = 0
while True:
    if time.clock() - t0 > 1:
        print(N * (N - 1) // 2)
        quit()
        
    madeMatch = False
    
    played = [False for i in range(N)]
    for i in range(N):
        if ind[i] == N-1 or played[i]: continue
        playAgainst = mat[i][ind[i]]
        if mat[playAgainst][ind[playAgainst]] == i and not played[playAgainst]:
            madeMatch = True
            played[i] = True
            played[playAgainst] = True

            ind[playAgainst] += 1
            ind[i] += 1
    if not madeMatch: break
    days += 1
    
if all(x == N-1 for x in ind):
    print(days)
else:
    print(-1)
### BUGGY CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
grid = []

for _ in range(n):
    s = ns()
    s = s+s
    grid.append(s)
    
for i in range(n):
    grid.append(grid[i])
    
vert = []
hrzn = []

for i in range(2*n):
    hrzn.append(grid[i])
    
for j in range(2*n):
    temp = ""
    for i in range(2*n):
        temp += grid[i][j:j+1]
        
    vert.append(temp)
    
    
ans = 0

for a in range(n):
    for b in range(n):
        
        ok = True
        for i in range(1,n):
            if vert[b][a+i:a+n] != hrzn[a][b+i:b+n]:
                ok = False
                
        if ok:
            ans += 1
            
print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())
 
n = ni()
grid = []
 
for _ in range(n):
    s = ns()
    s = s+s
    grid.append(s)
    
for i in range(n):
    grid.append(grid[i])
    
vert = []
hrzn = []
 
for i in range(2*n):
    hrzn.append(grid[i])
    
for j in range(2*n):
    temp = ""
    for i in range(2*n):
        temp += grid[i][j:j+1]
        
    vert.append(temp)
    
    
ans = 0
 
for a in range(n):
    for b in range(1):
        
        ok = True
        for i in range(n-1):
 
            if vert[b+i][a+i:a+n] != hrzn[a+i][b+i:b+n]:
                ok = False
                break
                
        if ok:
            ans += 1
            
print(ans*n)
### BUGGY CODE ###

from math import *
from decimal import *
N=int(input())
getcontext().prec=30
"""
l=[]
pf={}
m=N
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
print(pf)
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
print(l)
"""
a=1
while True:
    t=Decimal(1+8*a*N).sqrt()
    #print(t)
    #print(t.to_integral_value())
    n=t.to_integral_value()
    if ((n*n)%(1+8*a*N)==0)and(int(t)%2==1):
        print((int(t)-1)//2)
        break
    a=a+1


### FIXED CODE ###

from math import sqrt
from collections import deque
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
N=int(input())
def gcd_ext(a, b):
    x, y, lastx, lasty = 0, 1, 1, 0
    while b != 0:
        q = a // b
        a, b = b, a % b
        x, y, lastx, lasty = lastx - q * x, lasty - q * y, x, y
    return (lastx, lasty)
l=[]
pf={}
m=N*2
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
#print(pf)
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
#print(l)
d=deque()
d.append([])

for i in range(len(l)):
    x=list(range(values[i]+1))
    d2 = deque()
    #print(x)
    while len(d)>0:
        l=d.popleft()
        for j in x:
            l2=l[:]
            l2.append(j)
            d2.append(l2)
    d=d2
    #print(d)
ans=float("inf")
x=0
y=0
while len(d)>0:
    l=d.popleft()
    num=1
    res=1
    for i in range(len(l)):
        num=num*pow(keys[i],l[i])
        res=res*pow(keys[i],values[i]-l[i])
    #print(num,res)
    #x*num=k+1のときを考える
    if ggcd(num,res)==1:
        #x*num+y*res=1
        x,y=gcd_ext(num,res)
        if (x==0)or(y==0):
            x1=x+num*res
            y1=y+num+res
            ans=min(ans,x1*num-1)
            x2=x-num*res
            y2=x-num*res
            ans=min(ans,-x2*num)
        else:#どっちかは+でどっちかは-
            if x>y:
                ans=min(ans,x*num-1)
                x1=x-num*res
                ans=min(ans,-x1*num)
            else:
                x1=x+num*res
                ans=min(ans,x1*num-1)
                ans=min(ans,-x*num)
print(ans)
### BUGGY CODE ###

(n, k), p, c = [[*map(int, i.split())] for i in open(0)]
visit = [0] * n
visit[0] = 1
loop = [0] * n
count = a = 0
while True:
    a = p[a] - 1
    if visit[a]:
        if loop[a]:
            break
        count += c[a]
        loop[a] = 1
    visit[a] = 1

ln = sum(loop)


def solve(x, t):
    ans = c[p[x] - 1]
    l = True
    sub = 0
    while True:
        if loop[x] and l:
            if t > ln:
                if count >0:
                    sub += (t // ln - 1) * count
                t %=ln
                t += ln
            l = False
        if t < 1:
            ans = max(sub, ans)
            return ans
        x = p[x] - 1
        sub += c[x]
        t -= 1
        ans = max(sub, ans)


print(max(solve(i, k) for i in range(n)))


### FIXED CODE ###

(n, k), p, c = [[*map(int, i.split())] for i in open(0)]

def solve(x, t):
    visit = [0] * n
    visit[x] = 1
    loop = [0] * n
    count = 0
    ans = c[p[x] - 1]
    l = True
    sub = 0
    while True:
        x = p[x] - 1
        if l:
            if visit[x]:
                if loop[x]:
                    ln = sum(loop)
                    if t > l:
                        sub += (t//ln -1)*count*(count>0)
                        t %= ln
                        t += ln
                    l = False
                count += c[x]
                loop[x] = 1
            visit[x] = 1
        sub += c[x]
        t -= 1
        ans = max(sub, ans)
        if t < 1:
            return ans


print(max(solve(i, k) for i in range(n)))
### BUGGY CODE ###

import collections
import math

n = int(input())

m = list(map(str,input().split()))

c = dict(collections.Counter(m))
d = {}
hyouji = {}
def ans(a):
    if a<2:
        return 0
    else:
        return math.factorial(a) // (math.factorial(a - 2) * math.factorial(2))

cnt = 0
for i,j in c.items():
    n = ans(j)
    d[i] = n
    cnt += n


for k in m:
    if k in hyouji:
        print(hyouji[k])
    else: 
        if c[k] < 2:
            q = cnt
        elif c[k] == 2:
            q = cnt - 1
        else:
                q = cnt -d[k] + ans(c[k] - 1)

        hyouji[k] = q
        print(hyouji[k])

### FIXED CODE ###

import collections
import math

n = int(input())

m = list(map(str,input().split()))

c = dict(collections.Counter(m))
d = {}
hyouji = {}
def ans(a):
    if a<2:
        return 0
    else:
        return math.factorial(a) // (math.factorial(a - 2) * math.factorial(2))

cnt = 0
for i,j in c.items():
    n = ans(j)
    d[i] = n
    cnt += n


for k in m:
    if k in hyouji:
        print(hyouji[k])
    else: 
        if c[k] < 2:
            q = cnt
        elif c[k] == 2:
            q = cnt - 1
        else:
                q = cnt -d[k] + ans(c[k] - 1)

        hyouji[k] = q
        print(hyouji[k])
### BUGGY CODE ###

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

D = [[0] * 2 for _ in range(N)]

for i in range(N):
  D[i] = [i, A[i]]

D.sort(key = lambda x: x[1], reverse = True)

DP = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
  n, x = D[i]
  t = i + 1
  for j in range(t + 1):
    l = j
    r = t - j
    rr = N - 1 - r
    if l != 0:
      DP[l][r] = DP[l - 1][r] + abs(n - l + 1) * x
    if r != 0:
      DP[l][r] = max(DP[l][r], DP[l][r - 1] + abs(rr + 1 - n) * x)

ans = 0
for i in range(N + 1):
  ans = max(ans, DP[i][N - i])
print(ans)


### FIXED CODE ###

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

D = [[0] * 2 for _ in range(N)]

for i in range(N):
  D[i] = [i, A[i]]

D.sort(key = lambda x: x[1], reverse = True)

DP = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
  n, x = D[i]
  t = i + 1
  for j in range(t + 1):
    l = j
    r = t - j
    rr = N - 1 - r
    if l != 0:
      DP[l][r] = DP[l - 1][r] + abs(n - l + 1) * x
    if r != 0:
      DP[l][r] = max(DP[l][r], DP[l][r - 1] + abs(rr + 1 - n) * x)

ans = 0
for i in range(N + 1):
  ans = max(ans, DP[i][N - i])
print(ans)
### BUGGY CODE ###

import math
import sys

n,m = map(int, input().split())
a = [int(input()) for i in range(m)]

def nCr(n, r):
  c = math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
  return c

for i in range(m-1):
  if a[i] + 1 == a[i+1]:
    print('0')

    sys.exit()


a.insert(0, -1)
a.append(n+1)

cnt = 1

for i in range(m+1):
  step = (a[i+1] - 1) - (a[i] + 1)
  pattern = 1
  for j in range(1, step//2 + 1):
    k = j
    if j > (step - j) // 2:
      k = step - 2*j
    pattern += nCr(step - j, k)
  cnt *= pattern

print(cnt%1000000007)

### FIXED CODE ###

n,m = map(int, input().split())
step = []

now = 0
for i in range(m):
  next = int(input()) - 1
  step.append(next - now)
  now = next + 2

step.append(n-now)  
step.sort()

def fibo():
  s = []
  a = 1
  b = 1
  s.append(a)
  s.append(b)
  for i in range(n):
    c = a+b
    a = b
    b = c
    s.append(c)
  return s

ans = 1

if step[0] < 0:
  ans = 0

else:
  f = fibo()
  for i in step:
    ans *= f[i]

print(ans % 1000000007)
### BUGGY CODE ###

N = int(input())
S = input()
assert len(S) == N
count = 0
for i in range(0, len(S)-2):
  for j in range(i+1, len(S)-1):
    if S[i] == S[j]:
      continue
    SiSj = S[i] + S[j]
    if 'R' not in SiSj:
      Sk = 'R'
    elif 'G' not in SiSj:
      Sk = 'G'
    else:
      Sk = 'B'
    for k in range(j+1, len(S)):
      # RGBのどれかになるはず
      if Sk == S[k]:
        if j - i != k - j:
          count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = input()
assert len(S) == N
count = 0

# j-i = k-jを探す
for i in range(0, len(S)-2):
  for j in range(i+1, len(S)-1):
    k = j + (j - i)
    if k < len(S):
      if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
        count += 1
numR = 0
numG = 0
numB = 0
for s in S:
  if s == 'R':
    numR += 1
  elif s == 'G':
    numG += 1
  else:
    numB += 1

print(numR * numG * numB - count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
    N,M = map(int,input().split())
    G = [[] for _ in range(N+1)]
    
    for _ in range(M):
        x,y,z = map(int,input().split())
        x -= 1
        y -= 1
        G[x].append(y)
        G[y].append(x)
    
    seen = [False]*(N)
    ans = 0
    def dfs(v):
        if seen[v]:
            return
        seen[v] = True
        for nv in G[v]:
            dfs(nv)
    
    for v in range(N):
        if not seen[v]:
            dfs(v)
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

par = [-1]*(N+1)


def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True


def same(x,y):
    return find(x) == find(y)


def size(x):
    return -par[find(x)]

for i in range(M):
    x,y,z = map(int,input().split())
    unite(x,y)

ans = 0
counted = [False] * (N+1)
for i in range(1,N+1):
    root = find(i)
    if not counted[root]:
        ans += 1
        counted[root] = True
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
x = list(map(int,input().split()))
flag = True
for i in range(n+1):
    if i == n or x[i] > 0:
        x.insert(i,0)
        zahyou = i
        break
ans = 10**18
for i in range(k+1):
    mainasu = 0
    purasu = 0
    flag = True
    for j in range(k):
        a = zahyou-k+i+j
        if  a >= 0 and a < n:
            if x[a] < 0:
                mainasu += x[a+1]-x[a]
            else:
                purasu += x[a+1]-x[a]
        else:
            flag = False
    if mainasu != 0 and purasu != 0:
        purasu += min(mainasu,purasu)
    if flag:
        ans = min(ans,mainasu+purasu)
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
x = list(map(int,input().split()))
flag = True
for i in range(n+1):
    if i == n or x[i] > 0:
        x.insert(i,0)
        zahyou = i
        break
ans = 10**18
for i in range(k+1):
    flag = True
    if zahyou + i < n+1 and zahyou -k+i >= 0:
        mainasu = x[zahyou]-x[zahyou-k+i]
        purasu = x[zahyou+i]-x[zahyou]
        if mainasu != 0 and purasu != 0:
            purasu += min(mainasu,purasu)
        ans = min(ans,mainasu+purasu)
print(ans)
### BUGGY CODE ###

import itertools
import math

k=200
klis = list(range(1,k+1))
lis = list(itertools.product(klis, klis, klis))
temp = []
for i in range(len(lis)):
    temp.append(math.gcd(math.gcd(lis[i][0],lis[i][1]),lis[i][2]))

print(sum(temp))

### FIXED CODE ###

n = int(input())

all = int((n+1)*(n/2))
fizz = int(3*((n//3 + 1)*((n//3)/2)))
buzz = int(5*((n//5 + 1)*((n//5)/2)))
fizzbuzz = int(15*((n//15 + 1)*((n//15)/2)))

result =  all - fizz - buzz + fizzbuzz
print(result)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    sum = 0

    for i in range(len(A)):
        for j in range(i+1, len(A)):
            sum += A[i] * A[j]

    print(sum % MOD)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    MOD = 10 ** 9 + 7
    
    sum_a = sum(A)
    sum_squares = sum([a * a for a in A])
    
    ans = (sum_a ** 2 - sum_squares) // 2
    ans %= MOD

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