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

from itertools import permutations

def read_int_list():
    return list(map(int, input().split()))
    

def floyd_warshall():
            for k in range(N):
                for i in range(N):
                    for j in range(N):
                        dist[i][j] = min(dist[i][j],  dist[i][k] + dist[k][j])
                        
# def dfs(c, las, d):
#     global res
#     if c == R+1:
#         if res > d:
#             res = d
#         return
    
#     for i in range(1,R):
#         if used[i] != False:
#             used[i] = True
#             if las == -1:
#                 dfs(c+1,i,0)
#             else:
#                 dfs(c+1, i, d+dist[r[las]][r[i]])
#             used[i] = False
            
def permutation():
    global res
    for p in permutations(r):
        s = 0
        for i in range(R - 1):
            s += dist[p[i]][p[i + 1]]
        if s < res:
            res = s
            
N, M, R = (int(i) for i in input().split())
r = read_int_list()
r = [x - 1 for x in r]
used = [bool]*9
res = float('inf')
dist = [[float("inf") for i in range(201)] for i in range((201))]
for i in range(M):
    a, b, c = (int(i) for i in input().split())
    a -= 1
    b -= 1
    dist[a][b] = c
    dist[b][a] = c

floyd_warshall()
# dfs(1,-1,0)
permutation()
print(res)
    

### FIXED CODE ###

import sys
from itertools import permutations

def read_int_list():
    return list(map(int, input().split()))

 
def main():
    def floyd_warshall():
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dd = d[i][k] + d[k][j]
                    if dd < d[i][j]:
                        d[i][j] = dd
 
    n, m, r = read_int_list()
    v = read_int_list()
    v = [x - 1 for x in v]
    d = [[float('inf')] * n for i in range(n)]
    for i in range(n):
        d[i][i] = 0
    for i in range(m):
        a, b, c = read_int_list()
        a -= 1
        b -= 1
        d[a][b] = c
        d[b][a] = c
    floyd_warshall()
    res = float('inf')
    for p in permutations(v):
        s = 0
        for i in range(r - 1):
            s += d[p[i]][p[i + 1]]
        if s < res:
            res = s
    print(res)
 
 
main()
### BUGGY CODE ###

S = input()
Q = int(input())
rev = 0
for i in range(Q):
  query = input()
  if query == "1": rev += 1
  elif query[2] == "1" and rev % 2 == 0 or query[2] == "2" and rev % 2 == 1: S = query[4] + S
  else: S = S + query[4]
    
if rev % 2 == 1: S = S[::-1]
print(S)    
    

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
rev = 0
for i in range(Q):
  query = input()
  if query == "1": rev = 1 - rev 
  elif int(query[2]) + rev == 2: S.append(query[4])
  else:S.appendleft(query[4])
if rev == 1: S.reverse()  
print("".join(S))
### BUGGY CODE ###

#

import sys
input=sys.stdin.readline

kl=set()

def pf(n):
    ret={}
    for i in range(2,int((n)**0.5)+1):
        if n%i==0:
            cnt=0
            while(n%i==0):
                n/=i
                cnt+=1
            ret[i]=cnt
            kl.add(i)
    if n!=1:
        ret[int(n)]=1
        kl.add(int(n))
    return ret
            
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    p=[{} for i in range(N)]
    for i in range(N):
        p[i]=(pf(A[i]))
    lcm=1
    for i in kl:
        maxipow=0
        for j in range(N):
            maxipow=max(maxipow,p[j].get(i,0))
        lcm*=i**maxipow
    ans=0
    for i in range(N):
        bi=lcm//A[i]
        ans+=bi
        ans%=10**9+7
    print(ans)
    
    
    
if __name__=="__main__":
    main()


### FIXED CODE ###

#

import sys
from fractions import gcd
input=sys.stdin.readline

def main():
    MOD=10**9+7
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    l=(A[0]*A[1])//gcd(A[0],A[1])
    for i in range(2,N):
        l=(l*A[i])//gcd(A[i],l-A[i])
    l%=MOD
    ans=0
    for i in range(N):
        ans+=l*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

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

def c(index):
    return index%N

total_rain = sum(A) // 2

one = total_rain
for j in range(1, N-1, 2):
    one -= A[j]
rains = [0]*N
rains[0] = one*2

for m in range(1, N):
    rains[m] = (A[m-1] - rains[m-1]//2)*2

ans = ""
for rain in rains:
    ans+=str(rain)
    ans+=" "

print(ans)

### FIXED CODE ###

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

total_rain = sum(A) // 2

one = total_rain
for j in range(1, N-1, 2):
    one -= A[j]
rain = one*2
ans = str(rain)
prerain = rain

for m in range(1, N):
    rain = (A[m-1] - prerain//2)*2
    ans+=" "
    ans+=str(rain)
    prerain = rain

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

H,W=map(int,input().split())
S=[]
for h in range(H):
    Sh=list(input())
    newSh=[]
    for w in range(W):
        if Sh[w]=='#':
            newSh.append(1)
        else:
            newSh.append(0)
    Sh=newSh
    S.append(Sh)

L=[]
for h in range(H):
    Lh=[]
    a=0
    for w in range(W):
        if S[h][w]==0:
            a+=1
        else:
            a=0
        Lh.append(a)
    L.append(Lh)
    
R=[]
for h in range(H):
    Rh=[]
    a=0
    for w in range(W):
        if S[h][-(1+w)]==0:
            a+=1
        else:
            a=0
        Rh.append(a)
    Rh.reverse()
    R.append(Rh)

U=[]
for w in range(W):
    Uw=[]
    a=0
    for h in range(H):
        if S[h][w]==0:
            a+=1
        else:
            a=0
        Uw.append(a)
    U.append(Uw)
U=[[U[w][h] for w in range(W)] for h in range(H)]

D=[]
for w in range(W):
    Dw=[]
    a=0
    for h in range(H):
        if S[-(1+h)][w]==0:
            a+=1
        else:
            a=0
        Dw.append(a)
    Dw.reverse()
    D.append(Dw)
D=[[D[w][h] for w in range(W)] for h in range(H)]
    
maxScore=0
for h in range(H):
    for w in range(W):
        score=L[h][w]+R[h][w]+U[h][w]+D[h][w]-3
        if score>maxScore:
            maxScore=score
print(maxScore)

### FIXED CODE ###

import numpy as np
H,W=map(int,input().split())
S=[list(input()) for h in range(H)]
S=[[1 if s=='.' else 0 for s in S[h]] for h in range(H)]
S=np.array(S)
L=S.copy()
R=S.copy()
U=S.copy()
D=S.copy()
for w in range(1,W):
    L[:,w]=(L[:,w-1]+1)*S[:,w]
    R[:,-(1+w)]=(R[:,-w]+1)*S[:,-(1+w)]
for h in range(1,H):
    U[h,:]=(U[h-1,:]+1)*S[h,:]
    D[-(1+h),:]=(D[-h,:]+1)*S[-(1+h),:]
print(int((L+R+U+D).max())-3)
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
for i in range(N-L+1) : ans.append(str(min(A[i:i+L])))
print(" ".join(ans))

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

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

root = [[pow(10,9)]*n for _ in range(n)]

from collections import deque

root=[0]*n

for _ in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    if root[a]==0:
        root[a]=[b]
    else:
        root[a].append(b)

    if root[b]==0:
        root[b]=[a]
    else:
        root[b].append(a)
dist =[-1]*n
dist[0] = 0

q = deque([0])
prev=[-1] * n

while len(q)!=0:
    v = q[0]
    q.popleft()

    for j in root[v]:
        if dist[j]!=-1:
            continue
        else:
            dist[j] = dist[v] + 1
            prev[j] = v
            q.append(j)


for i in range(n):
    if i==0:
        print('Yes')
    else:
        print(prev[i]+1)


### FIXED CODE ###

n,m = map(int,input().split())
from collections import deque
r=[[] for i in range(n)]

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

# dist =[-1]*n
# dist[0] = 0

q = deque([0])
prev=[-1] * n

while q:
    v = q.popleft()

    for j in r[v]:
        if prev[j]==-1:
            prev[j] = v
            q.append(j)
            # dist[j] = dist[v] + 1
            

for i in range(n):
    if i==0:
        print('Yes')
    else:
        print(prev[i]+1)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
s=sum(a)
b=[0]*n
for i in range(n//2):
  b[2*i]=s-2*sum([a[(2*i+2*j+1)%n] for j in range(n//2)])
  b[2*i+1]=2*a[2*i]-b[2*i]
b[-1]=2*a[-1]-b[0]
print(*b)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[sum([a[i]*(1-i%2*2) for i in range(n)])]
for i in range(n-1):
  b+=[2*a[i]-b[-1]]
print(*b)
### BUGGY CODE ###

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

Visited = [0]*(M+1)
Mods = [0]*(M+1)
count = 0

for i in range (0, M):
	if (i**2)%M == i:
		Mods[i]=1
        
latest = 0
        
for i in range (0, N):
	if X in Mods:
		count+=((N-i)*X)
		for j in range (0, M+1):
			count+=(j*Visited[j])
		print(count)
		exit()
	if Visited[X] > 0:
		latest = X
		break
	Visited[X]+= 1
	X = (X**2)%M

P = sum(Visited)

for j in range (0, M+1):
	count+=(j*Visited[j])

Visited = [0]*(M+1)

if P == N:
	print(count)
	exit()

crouch = [0]
looper = 0
debu = 0 

for i in range (0, N-P):
	if Visited[X] > 0:
		looper = i
		debu = 1
		break
	else:
		crouch.append(X+crouch[-1])
	Visited[X]+= 1
	X = (X**2)%M
    
if debu == 0:
	for j in range (0, M+1):
		count+=(j*Visited[j])
	print(count)
	exit()
else:
	loops = 0
	for j in range (0, M+1):
		loops+=(j*Visited[j])
	count+=(loops*((N-P)//looper))
	count+=crouch[(N-P)%looper]
print(count)

### FIXED CODE ###

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

Visited = [0]*(M+1)
latestvisit = [0]*(M+1)
count = 0
latest = 0
proper = 0
        
for i in range (0, N):
	if Visited[X] > 0:
		latest = X
		latestvisit[X] = i
		proper = 1
		break
	latestvisit[X] = i
	Visited[X]+= 1
	X = (X**2)%M

for j in range (0, M+1):
	count+=(j*Visited[j])

if proper == 0:
	print(count)
	exit()
    
P = sum(Visited)
A = latestvisit[X]
B = latestvisit[(X**2)%M]
slouch = 0

for i in range (0, M):
	if latestvisit[i] >=B and latestvisit[i] <= A:
		slouch+=i

count+=((N-P)//(A-B+1))*slouch


for i in range (0, (N-P)%(A-B+1)):
	count+=X
	X = (X**2)%M

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

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

def solve():
    X, Y, Z, K = list(map(int, input().split(" ")))
    A = list(map(int, input().split(" ")))
    B = list(map(int, input().split(" ")))
    C = list(map(int, input().split(" ")))

    ans = []

    for x in range(X):
        for y in range(Y):
            for z in range(Z):
                ans.append(A[x]+B[y]+C[z])
    
    ans.sort(reverse=True)

    for i in range(0, K):
        print(ans[i])


if __name__ == "__main__":
    solve()


### FIXED CODE ###

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

def solve():
    """ TLE """
    X, Y, Z, K = list(map(int, input().split(" ")))
    A = list(map(int, input().split(" ")))
    B = list(map(int, input().split(" ")))
    C = list(map(int, input().split(" ")))
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)

    ans = []

    for x in range(X):
        for y in range(Y):
            ab = A[x] + B[y]
            for z in range(Z):
                if (x+1)*(y+1)*(z+1) > K:
                    break

                ans.append(ab + C[z])

    ans.sort(reverse=True)              
    
    for i in range(0, K):
        print(ans[i])


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

N,M,Q=map(int,input().split())
Town=[[int(i) for i in input().split()] for i in range(M)]
Town.sort(key=lambda x:x[0])

def BS_left(x,L,s):
  L_copy=L[:]
  left=0
  if L[s-1]<x:
    return s-1
  else:
    while s>2:
      if L_copy[s//2]<x:
        L_copy=L_copy[s//2:s]
        left+=s//2
        s=s-s//2
      else:
        L_copy=L_copy[0:s//2+1]
        s=s//2+1
    if L[left]>=x:
      return left-1
    else:
      return left

def BS_right(x,L,s):
  L_copy=L[:]
  right=s-1
  if L[0]>x:
    return 0
  else:
    while s>2:
      if L_copy[s//2]<=x:
        L_copy=L_copy[s//2:s]
        s=s-s//2
      else:
        L_copy=L_copy[0:s//2+1]
        right+=-s//2+1
        s=s//2+1
    if L[right]<=x:
      return right+1
    else:
      return right

ans=[0]*Q
for i in range(Q):
  p,q=map(int,input().split())
  for i in zip(*Town):
    TownL=i
    break
  a=BS_left(p,TownL,M)+1
  b=BS_right(q,TownL,M)
  newTown=Town[a:b]
  if b-a==0:
    print(0)
  else:
    newTown.sort(key=lambda x:x[1])
    e=0
    for i in zip(*newTown):
      if e==0:
        e+=1
      else:
        TownR=i
        break
    c=BS_right(q,TownR,b-a)
    if c==1 and TownR[0]>q:
      print(0)
    else:
      print(c)


### FIXED CODE ###

N,M,Q=map(int,input().split())
Train=[[int(i) for i in input().split()] for i in range(M)]
Map=[[0]*(N+1) for i in range(N+1)]
for i in Train:
  x,y=i[0],i[1]
  Map[y][x]+=1
for a in range(1,N+1):
  for b in range(1,N+1):
    if b<=N-1:
      Map[a][b+1]=Map[a][b]+Map[a][b+1]
    if a>=2:
      Map[a][b]=Map[a-1][b]+Map[a][b]
for i in range(Q):
  p,q=map(int,input().split())
  print(Map[q][q]-Map[q][p-1]-Map[p-1][q]+Map[p-1][p-1])
### BUGGY CODE ###

N,M=map(int,input().split())
path=[[0 if i<=j else float("inf") for i in range(N)] for j in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1][r-1]=c

seen=[]
dist=[float("inf")]*N
dist[0]=0
v=-1
while v!=N-1:
  v=-1
  for i in range(N):
    if i not in seen and v==-1:
      v=i
    if i not in seen and dist[i]<dist[v]:
      v=i
  seen.append(v)
  for i in range(N):
    dist[i]=min(dist[v]+path[v][i],dist[i])
    
if dist[N-1]==float("inf"):
  print(-1)
else:
  print(dist[N-1])

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
path=[[] for _ in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1].append([r,c])
for i in range(1,N):
  path[i].append([i,0])

dist=[float("inf")]*N
dist[0]=0
q=[[dist[i],i] for i in range(N)]
heapq.heapify(q)

while q:
  d,ind=heapq.heappop(q)
  if d<=dist[ind]:
    for i in range(len(path[ind])):
      r,c=path[ind][i]
      if dist[r-1]>d+c:
        dist[r-1]=d+c
        heapq.heappush(q,[dist[r-1],r-1])

if dist[N-1]==float("inf"):
  print(-1)
else:
  print(dist[N-1])
### BUGGY CODE ###

s = input()
n = len(s)
xy = tuple(map(int, input().split()))

dp = [[set() for i in range(4)] for j in range(n+1)]

dp[0][0].add((0,0))

for i in range(n):
    if s[i]=='F':
        for j in range(4):
            for x,y in dp[i][j]:
                if j ==0:
                    dp[i+1][j].add((x+1,y))
                elif j == 1:
                    dp[i+1][j].add((x,y+1))
                elif j == 2:
                    dp[i+1][j].add((x-1,y))
                else:
                    dp[i+1][j].add((x,y-1))
    else:
        for j in range(4):
            for x,y in dp[i][j]:
                if j!=3:
                    dp[i+1][j+1].add((x,y))
                    dp[i+1][j-1].add((x,y))
                else:
                    dp[i+1][0].add((x,y))
                    dp[i+1][j-1].add((x,y))



for i in range(4):
    if xy in dp[-1][i]:
        print('Yes')
        exit()
print('No')


### FIXED CODE ###

s = input()
n = len(s)
xy = list(map(int, input().split()))

right = 0
updown = []
rightleft = []

direction = 0
for i in range(n):
    if s[i]=='F':
        if direction == 0:
            right+=1
        elif direction == 1:
            updown[-1]+=1
        else:
            rightleft[-1]+=1
    else:
        if direction == 0 or direction == 2:
            direction = 1
            updown.append(0)
        else:
            direction = 2
            rightleft.append(0)

updown = [x for x in updown if x!=0]
rightleft = [x for x in rightleft if x!=0]

# 最初はx方向にしか進めないので補正
xy[0]-=right

# updownでyに行けるか？rightleftでxに行けるかを考えれば良い
dpy = [set() for i in range(len(updown)+1)]
dpy[0].add(0)
for i in range(len(updown)):
    for y in dpy[i]:
        dpy[i+1].add(y+updown[i])
        dpy[i+1].add(y-updown[i])

dpx = [set() for i in range(len(rightleft)+1)]
dpx[0].add(0)
for i in range(len(rightleft)):
    for x in dpx[i]:
        dpx[i+1].add(x+rightleft[i])
        dpx[i+1].add(x-rightleft[i])

if xy[1] in dpy[-1] and xy[0] in dpx[-1]:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

a,b,k = map(int,input().split())
src = [i for i in range(a,b+1)]
re = sorted(src, reverse=True)
if k > len(src):
    k = len(src)
li = set()
for ki in range(k):
    li.add(src[ki])
    li.add(re[ki])
for l in sorted(li):
    print(l)

### FIXED CODE ###

a,b,k = map(int,input().split())
if k > b-a+1:
    k = b-a+1
li = set()
for i in range(k):
    li.add(a+i)
    li.add(b-i)
for l in sorted(li):
    print(l)
### BUGGY CODE ###

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

PreYear = [[] for i in range(N)]
PY = [input().split(' ') for i in range(M)]
for i in range(M):
    Pi, Yi = PY[i]
    PreYear[int(Pi)-1].append(int(Yi))
order = []
for i in range(N):
    order.append(sorted(PreYear[i]))

for i in range(M):
    Pi, Yi = map(int,PY[i])
    count = order[Pi-1].index(Yi)
    count+=1
    print('{0:06d}{1:06d}'.format(Pi,count))

### FIXED CODE ###

from operator import itemgetter


N, M = map(int, input().split(' '))
data = []
for i in range(M):
    Pi, Yi = map(int, input().split(' '))
    data.append([i,Pi,Yi])

sorted_data = sorted(data, key=itemgetter(1,2))

codes = []
prev_p = 0
for i,p,y in sorted_data:
    if p!=prev_p:
        x = 1
        prev_p = p
    else:
        x+=1

    code = '{0:06d}{1:06d}'.format(p,x)
    codes.append([i,code])

sorted_codes = sorted(codes, key = itemgetter(0))

for code in sorted_codes:
    print(code[1])
### BUGGY CODE ###

n,m = map(int,input().split())
l,r = [],[]
for i in range(m):
    x,y = map(int,input().split())
    l.append(x)
    r.append(y)
cnt = 0
for i in range(1,n+1):
    for j in range(m):
        if l[j]>i or r[j]<i:
            break
    else:
        cnt+=1
print(cnt)

### FIXED CODE ###

n,m = map(int,input().split())
l,r = [],[]
for i in range(m):
    x,y = map(int,input().split())
    l.append(x)
    r.append(y)
print(max(0,min(r)-max(l)+1))
### BUGGY CODE ###

from random import randint

D = int(input())
C = [int(i) for i in input().split()]
S = [[int(i) for i in input().split()] for j in range(D)]

def score_calc(T):
    total = 0
    last = [0] * 26
    for i in range(1, D+1):
        t = T[i-1]
        total += S[i-1][t-1]
        last[t-1] = i
        for j in range(26):
            total -= C[j] * (i - last[j])
    return total

total = 0
last = [0] * 26
ans = []
for i in range(1, D+1):
    score = [0] * 26
    for t in range(26):
        score[t] += S[i-1][t]
        for j in range(26):
            if j != t:
                score[t] -= C[j] * (i - last[j])
    total += max(score)
    last[score.index(max(score))] = i
    ans.append(score.index(max(score))+1)

N = 100000
Q = [[randint(0, (D-1)), randint(0, 25)] for i in range(N)]
for d, q in Q:
    old = ans[d]
    ans[d] = q + 1
    if score_calc(ans) > total:
        total = score_calc(ans)
    else:
        ans[d] = old

for i in range(D):
    print(ans[i])


### FIXED CODE ###

D = int(input())
C = [int(i) for i in input().split()]
S = [[int(i) for i in input().split()] for j in range(D)]

total = 0
last = [0] * 26
ans = []
for i in range(1, D+1):
    score = [0] * 26
    for t in range(26):
        score[t] += S[i-1][t-1]
        for j in range(26):
            if j != t:
                score[t] -= C[j] * (i - last[j])
    total += max(score)
    last[score.index(max(score))] = i
    ans.append(score.index(max(score))+1)

for i in range(D):
    print(ans[i])
### BUGGY CODE ###

n=int(input())
S=input()
R=[]
G=[]
B=[]
for i in range(n):
    if S[i]=="R":
        R.append(i)
    elif S[i]=="G":
        G.append(i)
    else:
        B.append(i)
l=len(B)

ans=0
for i in range(len(R)):
    for j in range(len(G)):
        r=R[i]
        g=G[j]
        d=abs(r-g)
        cnt=0
        if d%2==0:
            if (r+g)//2 in B:
                cnt+=1
        if r<g:
            if g+d in B:
                cnt+=1
            if r-d in B:
                cnt+=1
        if r>g:
            if r+d in B:
                cnt+=1
            if g-d in B:
                cnt+=1
        ans+=l-cnt
print(ans)

### FIXED CODE ###

n=int(input())
S=input()
RGB=[[] for i in range(3)]
for i in range(n):
    if S[i]=="R":
        RGB[0].append(i)
    elif S[i]=="G":
        RGB[1].append(i)
    else:
        RGB[2].append(i)
L=[len(RGB[0]),len(RGB[1]),len(RGB[2])]
m=L.index(max(L))
A=[]
for i in range(3):
    if i==m:
        continue
    else:
        A.append(i)
C=RGB[A[0]]
D=RGB[A[1]]
E=RGB[m]

ans=0
for i in range(L[A[0]]):
    for j in range(L[A[1]]):
        r=C[i]
        g=D[j]
        d=abs(r-g)
        cnt=0
        if d%2==0:
            if (r+g)//2 in E:
                cnt+=1
        u=max(r,g)+d
        l=min(r,g)-d
        if 0<=u<=n-1:
            if u in E:
                cnt+=1
        if 0<=l<=n-1:
            if l in E:
                cnt+=1
        ans+=L[m]-cnt
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n = int(input())
A = list(map(int, input().split()))
#n, m = map(int, input().split())
#s = input()
#s,t = input().split()
#a = [int(input()) for _ in range(n)]
#
#readline = sys.stdin.readline
#n,m = [int(i) for i in readline().split()]
#ab = [[int(i) for i in readline().split()] for _ in range(n)]

MOD = 10**9+7

# tot = sum(A)

# ans = 0

# for a in A:
#     ans += a*(tot-a)
#     ans %= MOD

# ans //= 2
# ans %= MOD

ans = 0

for i in range(n):
    for j in range(i+1,n):
        ans += A[i]*A[j]
        ans %= MOD

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n = int(input())
A = list(map(int, input().split()))
#n, m = map(int, input().split())
#s = input()
#s,t = input().split()
#a = [int(input()) for _ in range(n)]
#
#readline = sys.stdin.readline
#n,m = [int(i) for i in readline().split()]
#ab = [[int(i) for i in readline().split()] for _ in range(n)]

MOD = 10**9+7

tot = sum(A)
tot %= MOD

ans = 0
rmv = 0

for a in A:
    rmv += a
    rmv %= MOD
    ans += a*(tot-rmv)
    ans %= MOD

print(ans)