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

# D Patisserie
N,M=map(int,input().split())
check=M+10 if M+10<=N else N
xyz_list,x_list,y_list,z_list=[],[],[],[]
for i in range(N):
    xyz_list.append(input().split())
for i in range(N):
    x_list.append([int(xyz_list[i][0]),i+1])
    y_list.append([int(xyz_list[i][1]),i+1])
    z_list.append([int(xyz_list[i][2]),i+1])
x_listn=x_list[:]
y_listn=y_list[:]
z_listn=z_list[:]
import itertools as itl
conb=[]
for i in range(check):
    conb.append(i)
conb=[x for x in itl.combinations(conb,M)]
sum_max=0

x_list.sort()
for l in range(2):
    for j in range(len(conb)):
        sum_x,sum_y,sum_z=0,0,0
        for k in conb[j]:
            num_comb=x_list[k][1]-1
            sum_x+=x_listn[num_comb][0]
            sum_y+=y_listn[num_comb][0]
            sum_z+=z_listn[num_comb][0]
        sum_xyz=abs(sum_x)+abs(sum_y)+abs(sum_z)
        if sum_xyz>sum_max:sum_max=sum_xyz
    x_list=x_list[::-1]
    
y_list.sort()
for l in range(2):
    for j in range(len(conb)):
        sum_x,sum_y,sum_z=0,0,0
        for k in conb[j]:
            num_comb=y_list[k][1]-1
            sum_x+=x_listn[num_comb][0]
            sum_y+=y_listn[num_comb][0]
            sum_z+=z_listn[num_comb][0]
        sum_xyz=abs(sum_x)+abs(sum_y)+abs(sum_z)
        if sum_xyz>sum_max:sum_max=sum_xyz
    y_list=y_list[::-1]
    
z_list.sort()
for l in range(2):
    for j in range(len(conb)):
        sum_x,sum_y,sum_z=0,0,0
        for k in conb[j]:
            num_comb=z_list[k][1]-1
            sum_x+=x_listn[num_comb][0]
            sum_y+=y_listn[num_comb][0]
            sum_z+=z_listn[num_comb][0]
        sum_xyz=abs(sum_x)+abs(sum_y)+abs(sum_z)
        if sum_xyz>sum_max:sum_max=sum_xyz
    z_list=z_list[::-1]
print(sum_max)

### FIXED CODE ###

# D Patisserie
import itertools as itl
#入力を取得
N,M=map(int,input().split())
check=M+10 if M+10<=N else N
xyz_list,x_list,y_list,z_list=[],[],[],[]
for i in range(N):
    xyz_list.append(input().split())
    
var_list=[x for x in itl.product([-1,1],repeat=3)]
sum_list=[]
for i in var_list:
    sort_list=[0,]*N
    for j in range(N):
        sort_list[j]=int(xyz_list[j][0])*i[0]+ int(xyz_list[j][1])*i[1]+ int(xyz_list[j][2])*i[2]
    sort_list.sort(reverse=True)
    sum_=0
    for j in range(M):
        sum_+=sort_list[j]
    sum_list.append(sum_)
    
sum_list.sort(reverse=True)
print(sum_list[0])
### BUGGY CODE ###

import sys
L, R = map(int,input().split())
a=[]

for i in range(L, R):
	for j in range(i+1,R+1):
		a.append((i*j)%2019)
		if 0 in a:
			print(0)
			sys.exit()
print(min(a))

### FIXED CODE ###

import sys
l,r = map(int,input().split())
a=[]

for i in range(l,r):
	for j in range(i+1,r+1):
		a.append((i*j)%2019)

		if (i*j)%2019 == 0:
			print(0)
			sys.exit()
print(min(a))
### BUGGY CODE ###

n = int(input())
s_li=[input() for i in range(n)]
new_li=[]
for i in range(n):
  new_li.append(sorted(list(s_li[i])))
ans = 0
for i in range(n):
  for j in range(i+1,n):
    if new_li[i] == new_li[j]:
      ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
dic = {}
ans = 0
for i in range(n):
  li_1 = list(input())
  li_1.sort()
  word = "".join(li_1)
  if word in dic:
    dic[word] += 1
  else:
    dic[word] = 1
for key in dic:
  s = dic[key]
  ans += s*(s-1)//2
print(ans)
### BUGGY CODE ###

# input here
_INPUT = """\
4
141421356 17320508 22360679 244949
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    n = int(input())
    a = list(map(int, input().split()))
    comb = list(itertools.combinations(a, 2))
    sum = 0
    for i in range(len(comb)):
        mult = comb[i][0] * comb[i][1]
        sum += mult

    print((sum % (10**9 + 7)))


if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

### FIXED CODE ###

# input here
_INPUT = """\
4
141421356 17320508 22360679 244949
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    n = int(input())
    a = list(map(int, input().split()))
    cumsum = list(itertools.accumulate(a))

    sum1 = 0
    for i in range(len(a)):
        mult = a[i] * (cumsum[n-1] - cumsum[i])
        sum1 += mult

    print((sum1 % (10**9 + 7)))


if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()
### BUGGY CODE ###

from math import floor, ceil


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    lower = 1
    upper = a[-1]
    while upper - lower >= 0.25 or floor(upper) != floor(lower):
        target = (lower + upper) / 2
        now = 0
        for i in range(n):
            now += ceil(a[i] / target) - 1
        if now > k:
            lower = target
        else:
            upper = target
    print(ceil(lower) if k > 0 else a[-1])


if __name__ == '__main__':
    main()



### FIXED CODE ###

from math import ceil


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    ng = 0
    ok = 10 ** 9 + 7
    while ok - ng > 1:
        mid = (ok + ng) // 2
        cnt = 0
        for i in range(n):
            cnt += (a[i] - 1) // mid
        if cnt <= k:
            ok = mid
        else:
            ng = mid
    print(ceil(ok) if k > 0 else a[-1])


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

N = int(input())
S = input()
S = [i for i in S]

T = 0
while len(S) != T:
    T = len(S)
    for i in range(0, len(S)-1 ):
        if S[i] == S[i+1]:
            S.pop(i)
            break

print(len(S))

### FIXED CODE ###

N = int(input())
S = input()

rslt = [S[0]]
S = [i for i in S[1:]]

for i in S:
    if rslt[-1] != i:
        rslt.extend(i)

print(len(rslt))
### BUGGY CODE ###

import bisect


def main():
    def isOK(score):
        count = 0
        for a in reversed(A):
            border_score = score - a
            index = bleft(A, border_score)
            count += N - index
            if count >= M:
                return True
        return False

    N, M = map(int, input().split())
    A = sorted(map(int, input().split()))
    ans = 0

    ng = A[-1] + A[-1] + 1
    ok = A[0] + A[0]
    bleft = bisect.bisect_left

    while(abs(ok-ng) > 1):
        #print(ok, ng)
        mid = (ok+ng) // 2
        f = isOK(mid)
        if f:
            ok = mid
        else:
            ng = mid
        #print(f)
        #print(ok, ng)

    min_score = float('inf')
    count = 0
    for a in A:
        index = bleft(A, ok-a)
        if index < N:
            min_score = min(a+A[index], min_score)
            ans += sum(A[index:]) + (N-index) * a
            count += N-index
    ans -= min_score * (count-M)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from bisect import bisect_left
import numpy


def main():
    def isOK(score):
        count = 0
        for a in reversed(A):
            border_score = score - a
            index = bleft(A, border_score)
            count += N - index
            if count >= M:
                return True
        return False

    N, M = map(int, input().split())
    A = sorted(map(int, input().split()))
    ans = 0

    ng = A[-1] + A[-1] + 1
    ok = A[0] + A[0]
    bleft = bisect_left

    while(abs(ok-ng) > 1):
        #print(ok, ng)
        mid = (ok+ng) // 2
        f = isOK(mid)
        if f:
            ok = mid
        else:
            ng = mid
        #print(f)
        #print(ok, ng)
    C = [0,] + A
    C = numpy.cumsum(C[::-1])
    #print(C)
    min_score = float('inf')
    count = 0
    for a in reversed(A):
        index = bleft(A, ok-a)
        if index < N:
            min_score = min(a+A[index], min_score)
            ans += C[N-index-1] + (N-index) * a
            count += N-index

    ans -= min_score * (count-M)
    print(ans)


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

import math
n = int(input())
s = int(math.sqrt(n))

for i in range(s,n+1):
    if n%i == 0:
        print(max(len(str(i)),len(str(n//i))))
        exit()

### FIXED CODE ###

import math
n = int(input())
s = int(math.sqrt(n))

for i in range(s,0,-1):
    if n%i == 0:
        print(max(len(str(i)),len(str(n//i))))
        exit()
### BUGGY CODE ###

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

N = int(input())
A = [deque(list(map(lambda x: int(x)-1, input().split()))) for _ in range(N)]
ans = 0
while any(A):
    ok = False
    used = [False] * N
    for i in range(N):
        a = A[i]
        if not a or used[i]:
            continue
        j = a[0]
        b = A[j]
        if not b or used[j]:
            continue
        if i == b[0]:
            ok = True
            A[i].popleft()
            A[j].popleft()
            used[i] = True
            used[j] = True
    if not ok:
        print(-1)
        exit()
    ans += 1
print(ans)


### FIXED CODE ###

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


def main():
    N = int(input())
    A = [deque(map(lambda x: int(x)-1, input().split())) for _ in range(N)]
    ans = 0
    used_prev = set(range(N))
    while any(A):
        used = set()
        for i in used_prev:
            a = A[i]
            if not a or i in used:
                continue
            j = a[0]
            b = A[j]
            if not b or j in used:
                continue
            if i == b[0]:
                A[i].popleft()
                A[j].popleft()
                used.add(i)
                used.add(j)
        if not used:
            ans = -1
            break
        used_prev = used
        ans += 1
    print(ans)


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

import sys
sys.setrecursionlimit(10**9)

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

SCORE=[[None for i in range(N+1)] for j in range(N+1)]

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番

    if i==j:
        return k
    if SCORE[i][j]!=None:
        return SCORE[i][j]+k
        

    if l==1:
        SCORE[i][j]=max(score(i+1,j,k+A[i],-l),score(i,j-1,k+A[j-1],-l))-k
        return SCORE[i][j]+k
    if l==-1:
        SCORE[i][j]=min(score(i+1,j,k-A[i],-l),score(i,j-1,k-A[j-1],-l))-k
        return SCORE[i][j]+k


print(score(0,N,0,1))

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

SCORE=[[None for i in range(N+1)] for j in range(N+1)]

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番
    #print(i,j,k,l)
    
    if SCORE[i][j]!=None:
        return SCORE[i][j]+k
    if i==j:
        SCORE[i][j]=0
        return k

        

    if l==1:
        SCORE[i][j]=max(score(i+1,j,k+A[i],-l),score(i,j-1,k+A[j-1],-l))-k
        return SCORE[i][j]+k
    if l==-1:
        SCORE[i][j]=min(score(i+1,j,k-A[i],-l),score(i,j-1,k-A[j-1],-l))-k
        return SCORE[i][j]+k



hand=N%2
for i in range(N+1):
    for j in range(N-i+1):
        score(j,j+i,0,(-1)**(j+j+i+hand))

print(SCORE[0][N])
### BUGGY CODE ###

n = int(input())
h = list(map(int,input().split()))
result = 0
for s in range(0,len(h)):
    count = 0
    for e in range(s,len(h)):
        if e  == len(h)-1:
            break
        if h[e] >= h[e+1]:
            count += 1
        else:
            break
    if count > result:
        result = count
print(result)

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
result = []
count = 0
for x in range(0,n-1):
    if h[x] >= h[x+1]:
        count += 1
    else:
        result.append(count)
        count = 0
result.append(count)
print(max(result))
### BUGGY CODE ###

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

T = [0]*(max(A)+1)
D = [0]*(max(A)+1)
for i in A:
    # iの2以上の倍数の値は1に
    for j in range(2*i, max(A)+1, i):
        T[j] = 1
    # ダブってる値は2以上に
    D[i] += 1

# Tが0かつDが1の数を数える
ans = 0
for i in A:
    if T[i] == 0 and D[i] == 1:
        ans += 1

print(ans)


### FIXED CODE ###

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

cnt = [0] * ((10 ** 6) + 1)

for elem in a:
    cnt[elem] += 1

unique = []

for i in range((10 ** 6) + 1):
    if cnt[i] == 1:
        unique.append(i)

cnt = [0] * ((10 ** 6) + 1)

a = list(set(a))

for elem in a:
    for m in range(elem * 2, (10 ** 6) + 1, elem):
        cnt[m] = 1

ans = 0
        
for elem in unique:
    if cnt[elem] == 0:
        ans += 1

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

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

num=[1,1,2]


mod=1000000007

count=0
jud=1
ans=1
for i in range(n+1):
	
	if i>2:
		num.append(1)
		num[i]=(num[i-1]+num[i-2])%mod

	if(jud==0 and i in a):
		print("0")
		break
	elif i in a:
		
		ans=(ans%mod)*(num[count-1]%mod)
		count=0
		jud=0
	elif(i==n):
		count+=1
		ans=(ans%mod)*(num[count-1]%mod)
		
		print(ans%mod)
	else:
		jud=1
		count+=1




### FIXED CODE ###

n,m=map(int,input().split())
a=[0]*(n+1)
for i in range(m):
	a[int(input())]=1


num=[1,1,2]


mod=1000000007

count=0
jud=1
ans=1
for i in range(n+1):
	
	if i>2:
		num.append(1)
		num[i]=(num[i-1]+num[i-2])%mod

	if(jud==0 and a[i]==1):
		print("0")
		break
	elif a[i]==1:
		ans=(ans%mod)*(num[count-1]%mod)
		count=0
		jud=0
	elif(i==n):
		count+=1
		ans=(ans%mod)*(num[count-1]%mod)
		print(ans%mod)
	else:
		jud=1
		count+=1
### BUGGY CODE ###

from collections import deque

dyx = ((0, 1), (0, -1), (1, 0), (-1, 0))
H, W = map(int, input().split())
edge = ['#'] * (W + 2)
field = [edge]
q = deque()

for i in range(H):
    line = input()
    field.append(['#'] + list(line) + ['#'])
    for j in range(W):
        if line[j] == '#':
            q.append((i + 1, j + 1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    if lv > res:
        res = lv

    if field[y + 1][x] == '.':
        field[y + 1][x] = '#'
        q.append((y + 1, x, lv + 1))

    if field[y - 1][x] == '.':
        field[y - 1][x] = '#'
        q.append((y - 1, x, lv + 1))

    if field[y][x+1] == '.':
        field[y][x+1] = '#'
        q.append((y, x+1, lv + 1))

    if field[y][x-1] == '.':
        field[y][x-1] = '#'
        q.append((y, x-1, lv + 1))

print(res)

### FIXED CODE ###

from collections import deque

dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
H, W = map(int, input().split())
edge = ['#']*(W+2)
field = [edge]
q = deque()

for i in range(H):
    field.append(['#'] + list(input()) + ['#'])
    for j in range(W):
        if field[i+1][j+1] == '#':
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    res = max(lv, res)

    for dy, dx in dyx:
        if field[y+dy][x+dx] == '.':
            field[y+dy][x+dx] = '#'
            q.append((y+dy, x+dx, lv+1))

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

import itertools

x = int(input())
max_c = int(x/100)

p_L = [i for i in range(100,106)]
a = list(itertools.combinations_with_replacement(p_L, max_c))

for val in a:
    if sum(val) == x:
        print(1)
        exit()
print(0)


### FIXED CODE ###

x = int(input())

product = list(range(100,105+1))

dp = [0] * 10**6

dp[0] = 1
for i in product:
    dp[i] = 1

for i in range(0,10**5+1):
    for j in product:
        if dp[i] == 1:
            dp[i+j] = 1

print(dp[x])
### BUGGY CODE ###

import itertools

N=int(input())
a_l=[int(i) for i in input().split()]

def xor(i,j):
    l=max(len(str(format(i,'b'))),len(str(format(j,'b'))))
    i2=str(format(i,'b').zfill(l))
    j2=str(format(j,'b').zfill(l))
    ans=0
    for k in range(l):
        if i2[k]!=j2[k]:
            ans+=2**(l-k-1)
    return ans

sum1=0
for (i,j) in itertools.product(range(N), range(N)):
    if i<j:
        sum1+=xor(a_l[i],a_l[j])
print(sum1%(7+10**9))

### FIXED CODE ###

n=int(input())
lis=list(map(lambda x:format(int(x),'b'),input().split()))
l=0
for i in range(n):
    l=max(l,len(lis[i]))

d0=[0]*60
d1=[0]*60

for i in range(n):
    lis[i]=lis[i].zfill(l)
    for j in range(l):
        if lis[i][-j-1]=='0':
            d0[j]+=1
        else:
            d1[j]+=1

ans=0
for i in range(60):
    ans+=(d0[i]*d1[i]*2**i)%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

n, p=map(int,input().split())
ans = 0
if n != 1:
    for i in range(1,int((p+1)**(1/2))+1):
        ni = i**n
        if p/ni >= 1 and p/ni == int(p/ni):
            ans = i
        elif p/ni < 1:
            break
    print(ans)
else:
    print(p)


### FIXED CODE ###

n, p=map(int,input().split())
ans = 0
if n != 1:
    for i in range(1,int((p+1)**(1/n))+1):
        ni = i**n
        if p/ni >= 1 and p/ni == int(p/ni):
            ans = i
        elif p/ni < 1:
            break
    print(ans)
else:
    print(p)
### BUGGY CODE ###

def main():
    n = int(input())
    ans = 0
    for i in range(1, n+1):
        for N in range(i, n+1, i):
            ans += N
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    ans = 0
    for i in range(1, n+1):
        # y = n // i
        # y = (y+1)*y*i//2
        ans += ((n//i)+1) * (n//i) * i // 2
    print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

war = {}
for i in range(M):
    a, b = map(int, input().split())
    if(a in war):
        if(b < war[a]):
            war[a] = b
    else:
        war[a] = b

ans = 0
bridge = [0 for i in range(N - 1)]
for a, b in war.items():
    for i in range(a, b):
        bridge[i - 1] += 1

while(war != {}):
    # print(war)
    ans += 1
    index = bridge.index(max(bridge))
    # print(index)
    for a, b in list(war.items())[:]:
        if(a <= index + 1 < b):
            war.pop(a)
            for i in range(a, b):
                bridge[i - 1] -= 1

print(ans)

### FIXED CODE ###

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

war = {}
for i in range(M):
    a, b = map(int, input().split())
    if(b in war):
        if(a > war[b]):
            war[b] = a
    else:
        war[b] = a

ans = 1
b_list = list(war.keys())
b_list = sorted(b_list)
r_bridge = b_list[0] - 1

for b in b_list:
    a = war[b]
    if(a <= r_bridge):
        continue
    else:
        r_bridge = b - 1
        ans += 1

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

m = [[0, 4, 8, 12, 3, 7, 11, 2, 6, 10],[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],[0, 10, 7, 4, 1, 11, 8, 5, 2, 12],[0, 9, 5, 1, 10, 6, 2, 11, 7, 3],[0, 12, 11, 10, 9, 8, 7, 6, 5, 4],[0, 3, 6, 9, 12, 2, 5, 8, 11, 1]]
S = list(input())
d = len(S)
dp = [[0] * 13 for _ in range(d)]
if S[0] == '?':
    for x in m[d%6]:
        dp[0][x] = 1
else:
    dp[0][m[d%6][int(S[0])]] = 1
for i in range(1,d):
    if S[i] == '?':
        for j in range(13):
            dp[i][j] = sum(dp[i-1][(13+j-x) % 13] for x in m[(d-i)%6]) % 1000000007
    else:
        for j in range(13):
            dp[i][j] = dp[i-1][(13+j-m[(d-i)%6][int(S[i])])%13]
print(dp[d-1][5])

### FIXED CODE ###

m = [[0, 4, 8, 12, 3, 7, 11, 2, 6, 10],[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],[0, 10, 7, 4, 1, 11, 8, 5, 2, 12],[0, 9, 5, 1, 10, 6, 2, 11, 7, 3],[0, 12, 11, 10, 9, 8, 7, 6, 5, 4],[0, 3, 6, 9, 12, 2, 5, 8, 11, 1]]
S = list(input())
d = len(S)
dp = [[0] * 13 for _ in range(d)]
if S[0] == '?':
    for x in m[d%6]:
        dp[0][x] = 1
else:
    dp[0][m[d%6][int(S[0])]] = 1
for i in range(1,d):
    if S[i] == '?':
        for j in range(13):
            dp[i][j] = sum(dp[i-1][(13+j-x) % 13] for x in m[(d-i)%6]) % 1000000007
    else:
        for j in range(13):
            dp[i][j] = dp[i-1][(13+j-m[(d-i)%6][int(S[i])])%13]
print(dp[d-1][5])
### BUGGY CODE ###

from scipy.misc import comb

X, Y = map(int, input().split())
MOD = 10**9+7

if (X+Y) % 3:
    print(0)
    exit()

N = (X+Y) // 3

A = X - N
B = Y - N

ans = comb(A+B, A, exact=True) % MOD
print(ans)



### FIXED CODE ###

def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    return [w[0], w[1]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m


X, Y = map(int, input().split())
MOD = 10 ** 9 + 7

if (X + Y) % 3:
    print(0)
    exit()

n = (X + Y) // 3
nx, ny = X - n, Y - n

if nx < 0 or ny < 0:
    print(0)
    exit()

ans = 1
for i in range(1, nx + ny + 1):
    ans = ans * i % MOD
for i in range(1, nx + 1):
    ans = ans * mod_inv(i, MOD) % MOD
for i in range(1, ny + 1):
    ans = ans * mod_inv(i, MOD) % MOD

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

import sys
input = sys.stdin.buffer.readline

def f(g: list, deg: list):
	l = len(g)
	depth = [0] * l
	ret = []
	q = []
	for i, d in enumerate(deg):
		if not d:
			ret.append(i)
			q.append(i)
	while q:
		cur = q.pop(0)
		for nxt in g[cur]:
			deg[nxt] -= 1
			if not deg[nxt]:
				depth[nxt] = depth[cur] + 1
				ret.append(nxt)
				q.append(nxt)
	if l > len(ret):
		return False
	return max(depth)

def label(a, b, n):
	if a > b:
		a, b = b, a
	return (a - 1) * (2 * n - a) // 2 + b - a - 1


def main():
	n = int(input())
	g = [[] for _ in range(n * (n - 1) // 2)]
	deg = [0] * (n * (n - 1) // 2)
	for i in range(1, n + 1):
		l = list(map(int, input().split()))
		for x, y in zip(l, l[1:]):
			t = label(i, y, n)
			g[label(i, x, n)].append(t)
			deg[t] += 1
	depth = f(g, deg)
	if not depth:
		print(-1)
		exit()
	print(depth + 1)

if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def f(g: list, deg: list):
	l = len(g)
	depth = [0] * l
	ret = []
	q = []
	for i, d in enumerate(deg):
		if not d:
			ret.append(i)
			q.append(i)
	while q:
		cur = q.pop(0)
		for nxt in g[cur]:
			deg[nxt] -= 1
			if not deg[nxt]:
				depth[nxt] = depth[cur] + 1
				ret.append(nxt)
				q.append(nxt)
	if l > len(ret):
		return False
	return max(depth)

def label(a, b, n):
	if a > b:
		a, b = b, a
	return (a - 1) * (2 * n - a) // 2 + b - a - 1


def main():
	n = int(input())
	g = [[] for _ in range(n * (n - 1) // 2)]
	deg = [0] * (n * (n - 1) // 2)
	for i in range(1, n + 1):
		l = list(map(int, input().split()))
		for x, y in zip(l, l[1:]):
			t = label(i, y, n)
			g[label(i, x, n)].append(t)
			deg[t] += 1
	depth = f(g, deg)
	if not depth:
		print(-1)
		exit()
	print(depth + 1)

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

N = int(input())

input_1 = input()
input_2 = input_1.split()

A = map(int, input_2)

def equal(num):
    return num
A = [equal(x) for x in A]

ans = 0

for l in range(N):
    ans += A.count(A[l]) - 1

ans = ans / 2
re = ans

for k in range(N):
    ans -= A.count(A[k]) - 1

    print(int(ans))

    ans = re

### FIXED CODE ###

#TLE
n = int(input())
a = input().split()
ans = 0
import collections
dic = collections.Counter(a)
for i in dic.values():
    ans += i * (i-1)
ans /= 2
for i in range(n):
    print(int(ans - dic[a[i]] + 1))
### BUGGY CODE ###

n = int(input())

ans = 0

for i in range(n):
    ans += i
    
print(ans)

### FIXED CODE ###

n = int(input())

ans = ((n+1)*n)//2-n
    
print(int(ans))