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

import fractions
from functools import reduce


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


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

    AN_lcm = lcm_list(AN)

    ans = 0
    for A in AN:
        ans += AN_lcm // A
        ans %= 10**9 + 7

    print(ans)


main()


### FIXED CODE ###

import fractions
from functools import reduce

MOD = 10**9 + 7


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


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

    AN_lcm = lcm_list(AN) % MOD

    ans = 0
    for A in AN:
        ans += AN_lcm * modinv(A, MOD)
        ans %= MOD

    print(ans)


main()
### BUGGY CODE ###

import math
import copy

N = int(input())
As = input().split()
A = [0 for i in range(N)]
for i in range(N):
  A[i] = int(As[i])

# count number of each label appearing
labels = {}
for i,A_i in enumerate(A):
  if A_i in labels:
    labels[A_i] += 1
  else:
    labels[A_i] = 1

answer = [-1 for i in range(N)]
spoiler = {}
for k in range(N):
  if A[k] in spoiler:
    answer[k] = spoiler[A[k]]
  else:
    labels_now = copy.copy(labels)
    labels_now[A[k]] -= 1
    appnums = list(labels_now.values())
    answer[k] = 0
    for appnum in appnums:
      if appnum>1: answer[k] += int(appnum*(appnum-1)/2)
    spoiler[A[k]] = answer[k]

for k in range(N):
  print(answer[k])


### FIXED CODE ###

import math
import copy
import numpy as np

N = int(input())
As = input().split()
A = [0 for i in range(N)]
for i in range(N):
  A[i] = int(As[i])

# relabel A's elements
A_unique = list(set(A))
num_unique = len(A_unique)
to_unique = {}
for i,a in enumerate(A_unique):
  to_unique[a] = i
for i in range(N):
  A[i] = to_unique[A[i]]

# count number of each label appearing
counts = [0 for i in range(num_unique)]
for _,A_i in enumerate(A):
  counts[A_i] += 1
answer_total = 0
for count in counts:
  answer_total += int(count*(count-1)/2)

spoiler = [-1 for i in range(num_unique)]
for k in range(N):
  if spoiler[A[k]]<0:
    answer_k = answer_total - (counts[A[k]]-1)
    spoiler[A[k]] = answer_k
  else:
    answer_k = spoiler[A[k]]
  print(answer_k)
### BUGGY CODE ###

#coding:utf-8
N,Y=map(int,input().split())
a=[int(x) for x in input().split()]
for b in range(Y):
  a[a.index(max(a))]=a[a.index(max(a))]//2
print(sum(a))


### FIXED CODE ###

import heapq

N,M=( int(x) for x in input().split())
A=[int(s)*-1 for s in input().split()]

heapq.heapify(A)

for i in range(M):
    A_max=heapq.heappop(A)*-1
    heapq.heappush(A,(A_max//2)*-1)    
print(sum(A)*-1)
### BUGGY CODE ###

S = input()
ans = 0
for i in range(len(S)):
  if S[i] == 'W':
    ans+=S[:i+1].count('B')
print(ans)

### FIXED CODE ###

S = input()
ans = 0
tmp = 0
for i in range(len(S)):
  if S[i] == 'W':
    ans+=i-tmp
    tmp+=1
print(ans)
### BUGGY CODE ###

def main():
    s = input()
    K = int(input())
    a = ord("a")
    code = [ord(c) - a for c in s]
    for i in range(len(s)):
        x = 26 - code[i] % 26
        if x <= K:
            code[i] = 0
            K -= x
    code[-1] = code[-1] + K % 26
    ans = ""
    for x in code:
        ans += chr(a + x)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    s = input()
    K = int(input())
    a = ord("a")
    code = [ord(c) - a for c in s]
    for i in range(len(s)):
        x = (26 - code[i]) % 26
        if x <= K:
            code[i] = 0
            K -= x
    code[-1] = code[-1] + K % 26
    ans = "".join([chr(a + x) for x in code])
    print(ans)


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

from collections import defaultdict as dict
d = dict(int)

N, M = map(int,input().split())
A = [list(map(int,input().split())) for z in range(M)]
a = sorted(A)
b = [[0, 0] for z in range(M + 1)]
for i in range(1, M + 1):
    x, y = a[i - 1]
    if b[i - 1][0] != x:
        cnt = 1

    b[i] = [x, str(x).zfill(6) + str(cnt).zfill(6)]
    cnt += 1

for j in range(M):
    print(b[a.index(A[j]) + 1][1])



### FIXED CODE ###

N, M = [int(_) for _ in input().split()]
PY = [[int(_) for _ in input().split()] + [_] for _ in range(M)]
# 2番目のKeyでソート
PY.sort(key = lambda x : x[1])
# 順番カウント用
cnt = [0] * (N + 1)
ans = [""] * M

for p, y, i in PY:
    # 何番目かカウント
    cnt[p] += 1
    # 答え
    ans[i] = str(p).zfill(6) + str(cnt[p]).zfill(6)

print("\n".join(ans))
### BUGGY CODE ###

import numpy as np

n,k=map(int,input().split())
v=[0 for _ in range(n)]
w=[0 for _ in range(n)]
for i in range(n):
	w[i],v[i] = map(int,input().split())

dp = np.full((n+1, k+1), 0, dtype=np.int64)

for i in range(n):
	for j in range(k+1):
		if j-w[i] < 0:
			dp[i+1][j] = dp[i][j]
		else:
			dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
print(dp[n][k])

### FIXED CODE ###

n,k=map(int,input().split())
v=[0 for _ in range(n)]
w=[0 for _ in range(n)]
for i in range(n):
	w[i],v[i] = map(int,input().split())

dp = [[0 for i in range(k+1)] for j in range(n+1)]

for i in range(n):
	for j in range(k+1):
		if j-w[i] < 0:
			dp[i+1][j] = dp[i][j]
		else:
			dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
print(dp[n][k])
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))
    ans = 0
    for i in range(n):
        for j in range(i+a[i],n):
            if a[i]+a[j]==j-i:
                ans+=1
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))
    Ilis = {}
    Jlis = {}
    for i in range(n):
        k = a[i]+i+1
        l = i-a[i]+1
        if k not in Ilis.keys():
            Ilis[k] = 1
        else:
            Ilis[k]+=1
        if l not in Jlis.keys():
            Jlis[l]=1
        else:
            Jlis[l]+=1
    ans = 0
    for i in Ilis.keys():
        if i in Jlis.keys():
            ans += Ilis[i]*Jlis[i]
    print(ans)

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

import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)
    IV, IW = [], []

    H = min(N + 1, 1 << 10)
    Hb = (H - 1).bit_length()
    dp = [[0] * (MX + 1) for _ in range(H)]
    i = 1
    for v, w in zip(data, data):
        if i < H:
            dpi = dp[i]
            dpip = dp[i >> 1]
            for j in range(w):
                dpi[j] = dpip[j]
            for j in range(w, MX + 1):
                dpi[j] = max(dpip[j], dpip[j - w] + v)
        else:
            IV.append(v)
            IW.append(w)
        i += 1
        if i > N:
            break

    Q = next(data)
    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue

        item_values = []
        item_weights = []
        while v >= H:
            item_values.append(IV[v - H])
            item_weights.append(IW[v - H])
            v >>= 1

        l = len(item_values)
        V = [0] * (1 << l)
        W = [0] * (1 << l)
        ans = [dp[v][L]]
        for i in range(1, 1 << l):
            msb = i & (-i)
            msbb = msb.bit_length() - 1
            V[i] = V[i - msb] + item_values[msbb]
            W[i] = W[i - msb] + item_weights[msbb]
            if W[i] <= L:
                ans.append(V[i] + dp[v][L - W[i]])
        print(max(ans))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)

    H = min(N + 1, 1 << 10)
    dp = [None] * H
    dp[0] = [0] * (MX + 1)
    IV, IW = [], []
    i = 1
    for v, w in zip(data, data):
        if i < H:
            dpi = dp[i >> 1][:]
            dp[i] = dpi
            for j in range(MX, w - 1, -1):
                dpi[j] = max(dpi[j], dpi[j - w] + v)
        else:
            IV.append(v)
            IW.append(w)
        i += 1
        if i > N:
            break

    Q = next(data)
    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue

        item_values = []
        item_weights = []
        while v >= H:
            item_values.append(IV[v - H])
            item_weights.append(IW[v - H])
            v >>= 1

        l = len(item_values)
        V = [0] * (1 << l)
        W = [0] * (1 << l)
        ans = dp[v][L]
        for i in range(1, 1 << l):
            msb = i & (-i)
            msbb = msb.bit_length() - 1
            wi = W[i - msb] + item_weights[msbb]
            W[i] = wi
            if wi <= L:
                vi = V[i - msb] + item_values[msbb]
                ans = max(ans, vi + dp[v][L - wi])
                V[i] = vi
        print(ans)

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

n,q=map(int,input().split())
if n==1:
    for i in range(q):
        v,w=map(int,input().split())
        print(min(v,w))
else:
    for i in range(q):
        v,w=map(int,input().split())
        while v!=w:
            if v>w:v,w=w,v
            w=(w+n-2)//n
        print(v)

### FIXED CODE ###

n,q=map(int,input().split())
if n==1:
    for i in range(q):
        v,w=map(int,input().split())
        print(min(v,w))
else:
    for i in range(q):
        v,w=map(int,input().split())
        while v!=w:
            if v>w:v,w=w,v
            w=(w+n-2)//n
        print(v)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

h,w = map(int, input().split())
board = [list(input()) for i in range(h)]
#print(*board, sep="\n")
dxdy = [(0,1),(1,0),(0,-1),(-1,0)]

def dfs(i, j, k, prev):
    if used[i][j] or board[i][j] == prev:
        return
    used[i][j] = 1
    k[board[i][j] == "."] += 1
    for dx, dy in dxdy:
        nx, ny = i+dx, j+dy
        if 0 <= nx < h and 0 <= ny < w and board[nx][ny] != board[i][j]:
            dfs(nx,ny,k,board[i][j])

used = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        k = [0]*2
        dfs(i,j,k, "1")
        ans += k[0]*k[1]
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

h,w = map(int, input().split())
board = [[int(j=="#") for j in input()] for i in range(h)]
dxdy = [[0,1], [0,-1], [1,0], [-1,0]]

def dfs(i, j, k, prev):
    if used[i][j] or board[i][j] == prev:
        return
    used[i][j] = 1
    k[board[i][j]] += 1
    for dx, dy in dxdy:
        nx, ny = i+dx, j+dy
        if 0 <= nx < h and 0 <= ny < w and not used[nx][ny] and board[nx][ny] != board[i][j]:
            dfs(nx,ny,k,board[i][j])

used = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        k = [0]*2
        dfs(i,j,k, -1)
        ans += k[0]*k[1]
print(ans)
### BUGGY CODE ###

import math
def sieve(n, done):
    for i in range(n, 10**6+1, n):
        done[i] = 1

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

ans = 0
done = [0] * (10 ** 6 + 1)

for i in range(n):
    num = a[i]
    if i < n-1 and a[i] == a[i+1]:
        sieve(num, done)
        continue
    
    if not done[num]:
        sieve(num, done)
        ans += 1

print(ans)


### FIXED CODE ###

import math
def sieve(n, done):
    for i in range(n, 10**6+1, n):
        done[i] = 1

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

ans = 0
done = [0] * (10 ** 6 + 1)

for i in range(n):
    num = a[i]
    if i < n-1 and a[i] == a[i+1]:
        if i > 0 and a[i] == a[i-1]:
            continue
        sieve(num, done)
        continue
    
    if not done[num]:
        sieve(num, done)
        ans += 1

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

import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

def LI(): return list(map(int, stdin.readline().split()))
def LS(): return list(stdin.readline())

from collections import Counter
n = int(input())
s = Counter([input() for i in range(n)])
ans = [k for k,v in s.items() if v==max(s.values())]
print('\n'.join(sorted(ans)))

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

def LI(): return list(map(int, stdin.readline().split()))
def LS(): return list(stdin.readline())

from collections import Counter
n = int(input())
s = Counter([input() for i in range(n)])
high = max(s.values())
ans = [k for k,v in s.items() if v==high]
print('\n'.join(sorted(ans)))
### BUGGY CODE ###

N, M = map(int,input().split())
lst=[None]*M
for i in range(M):
    p, S=input().split()
    lst[i]=(int(p), S)

#print(N, M, lst)
#count AC
AC_count = 0
WA_count = 0
for i in range(1, N+1):
    if (i, 'AC') in lst:
        AC_count += 1
        success = lst.index((i, 'AC'))
        WA_count+=lst[:success].count((i, 'WA'))

print(AC_count, WA_count)

### FIXED CODE ###

N, M = map(int,input().split())
lst=[None]*M
for i in range(M):
    p, S=input().split()
    lst[i]=(int(p), S)

stop_set=set()

WA_count=0
AC_count=0
from collections import defaultdict
WA_dict = defaultdict(lambda: 0)

for el in lst:
    if not el[0] in stop_set:
        if el[1]=='AC':
            AC_count+=1
            stop_set.add(el[0])
        else:
            WA_dict[el[0]] +=1
#print(dict(WA_dict))

new_set=set(WA_dict.keys())&stop_set
#print(new_set)
WA_count=sum([WA_dict[i] for i in new_set])
print(AC_count, WA_count)
### BUGGY CODE ###

#!/usr/bin/env python3
import bisect

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    S = list(input())
    Q = int(input())

    alphabets = [chr(i) for i in range(ord("a"), ord("a")+26)]

    L = {x:[] for x in alphabets} # i番目のリストは、アルファベットが現れるインデックスのリストを持つ。
    for idx, s in enumerate(S):
        L[s].append(idx)

    for _ in range(Q):
        row = input().split()
        if row[0] == '1':
            x, y, z = int(row[0]), int(row[1])-1, row[2]
        elif row[0] == '2':
            x, y, z = int(row[0]), int(row[1]) - 1, int(row[2]) - 1

        if x == 1:
            target = S[y]
            idx_del = bisect.bisect_left(L[target], y)
            if idx_del < len(L[target]):
                L[target].pop(idx_del)
            bisect.insort(L[z], y)
            S[y] = z
        elif x == 2:
            answer = 0
            for alphabet in alphabets:
                left = bisect.bisect_left(L[alphabet], y)
                if left < len(L[alphabet]) and y <= L[alphabet][left] <= z:
                    answer += 1
            print(answer)

    # Failed to predict input format
    pass

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import bisect

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    S = list(input())
    Q = int(input())

    L = [[] for x in range(26)] # i番目のリストは、アルファベットが現れるインデックスのリストを持つ。

    for idx, s in enumerate(S):
        L[ord(s)-ord("a")].append(idx)

    for _ in range(Q):
        row = input().split()
        if row[0] == '1':
            y, z = int(row[1])-1, row[2]
            if S[y] != z:
                idx_target = ord(S[y]) - ord("a")
                idx_del = bisect.bisect_left(L[idx_target], y)
                if idx_del < len(L[idx_target]):
                    L[idx_target].pop(idx_del)
                bisect.insort(L[ord(z) - ord("a")], y)
                S[y] = z

        elif row[0] == '2':
            y, z = int(row[1]) - 1, int(row[2]) - 1
            answer = 0
            for idx_alphabet in range(26):
                left = bisect.bisect_left(L[idx_alphabet], y)
                if left < len(L[idx_alphabet]) and y <= L[idx_alphabet][left] <= z:
                    answer += 1
            print(answer)

    # Failed to predict input format
    pass

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

n=int(input())
ans=1
li = input().split()
for i in li:
  ans*=int(i)
  if ans>1000000000000000000:
    ans*=-1

if ans<0:
  ans=-1
print(ans)

### FIXED CODE ###

n=int(input())
ans=1
zero=False
minus=False
li = input().split()
for i in li:
  a=int(i)
  if a==0:
    zero=True
    break
  if minus:
    continue
  ans*=a
  if ans>1000000000000000000:
    minus=True

if minus:
  ans=-1
if zero:
  ans=0
print(ans)
### BUGGY CODE ###

a,b,c,d=map(int,input().split())
ans=0
for i in range(a,b+1):
  if i%c!=0 and i%d!=0:
    ans+=1
print(ans)
  


### FIXED CODE ###

a,b,c,d=map(int,input().split())
if d>c:
  euclid2,euclid1=c,d
  e1,e2=euclid1,euclid2
  while not euclid2==0:
    euclid1=euclid1%euclid2
    euclid1,euclid2=euclid2,euclid1
    cd=c*d//euclid1
else:
  euclid2,euclid1=d,c
  e1,e2=euclid1,euclid2
  while not euclid2==0:
    euclid1=euclid1%euclid2
    euclid1,euclid2=euclid2,euclid1
    cd=c*d//euclid1
  
c1=(a-1)//c+1
c2=(b-c1*c)//c+1
d1=(a-1)//d+1
d2=(b-d1*d)//d+1
cd1=(a-1)//cd+1
cd2=(b-cd1*cd)//cd+1  
print(b-a+1-c2-d2+cd2)
### BUGGY CODE ###

n, m = map(int, input().split())
numlist = []
record = [0] * (n-1)
route = []
for i in range(m):
    temp = list(map(int, input().split()))
    if(temp[0] == 1):
        m -= 1
        record[temp[1] - 2] = 1
        route.append(temp[1])
    elif(temp[1] == 1):
        m -= 1
        record[temp[0] - 2] = 1
        route.append(temp[0])
    else:
        numlist += temp
newlist = []
flag = 1
for i in record:
    flag *= i 
while(flag == 0):
    newroute = []
    for i in range(len(route)):
        for j in range(m):
            if(numlist[j * 2] == route[i]):
                m -= 1
                if(record[numlist[j * 2 + 1] - 2] == 0):
                    record[numlist[j * 2 + 1] - 2] = route[i]
                newroute.append(numlist[j * 2 + 1])
            elif(numlist[j * 2 + 1] == route[i]):
                m -= 1
                if(record[numlist[j * 2] - 2] == 0):
                    record[numlist[j * 2] - 2] = route[i]
                newroute.append(numlist[j * 2])
            else:
                newlist += numlist[j*2:j*2 + 2]
        numlist = newlist
        newlist = []
    route = newroute
    flag = 1
    for i in record:
        flag *= i
print("Yes")
for i in record:
    print(i)

### FIXED CODE ###

import queue
n, m = map(int, input().split())
graph = [[] for i in range(n)]
depth = [-1] * n
route = []
result = [0] * (n - 1)
for i in range(m):
    temp = list(map(int, input().split()))
    graph[temp[0] - 1].append(temp[1] - 1)
    graph[temp[1] - 1].append(temp[0] - 1)
    route.append(temp)
q = queue.Queue()
q.put(0)
depth[0] = 0
for i in range(n-1):
    item = q.get()
    for j in graph[item]:
        if(depth[j] == -1):
            q.put(j)
            depth[j] = depth[item] + 1
print("Yes")
for i in route:
    if(i[0] == 1):
        result[i[1] - 2] = 1
    elif(i[1] == 1):
        result[i[0] - 2] = 1
    elif(depth[i[0] - 1] - depth[i[1] - 1] == 1):
        result[i[0] - 2] = i[1]
    elif(depth[i[1] - 1] - depth[i[0] - 1] == 1):
        result[i[1] - 2] = i[0]
for i in result:
    print(i)
### BUGGY CODE ###

N=int(input())
a=[int(i) for i in input().split()]
for j in range(N):
    print(a.count(j+1))


### FIXED CODE ###

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

d = {}

for i in range(N - 1):
    if A[i] in d:
        d[A[i]].append(i + 2)
    else:
        d[A[i]] = [i + 2]

for i in range(1, N + 1):
    if i in d:
        print(len(d[i]))
    else:
        print(0)
### BUGGY CODE ###

def resolve():
    N = int(input())
    P_list = list(map(int, input().split()))

    answer = 0

    for i in range(1, len(P_list)+1):
        #print("i:" + str(i))
        ok_flag = True
        for j in range(1, i+1):
            #print("j:" + str(j))
            #print(" P_list[i-1]:" + str(P_list[i-1]))
            #print(" P_list[j-1]:" + str(P_list[j-1]))
            if P_list[i-1] <= P_list[j-1]:
                ok_flag = True
            else:
                ok_flag = False
                break
        if ok_flag:
            answer += 1

    print(answer)

 
if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    p = input().split()
    num = 0
    mini = int(p[0])
    for i in range(N):
        if int(p[i])<=mini:
            num+=1
            mini=int(p[i])
    print(num)
 
 
if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

n=int(input())
a=[list(map(int,input().split()))for _ in range(n)]
calc=lambda u,v:min(u,v)*n+max(u,v)
edge=[[]for _ in range(n*n)]
for i in range(n):
  for j in range(1,n-1):
    u,v=calc(a[i][j-1]-1,i),calc(a[i][j]-1,i)
    edge[u].append(v)
from collections import deque
def find_loop(n,e):
  x=[0]*n
  d=deque()
  t=[]
  c=0
  for i in range(n):
    for j in e[i]:x[j]+=1
  for i in range(n):
    if x[i]==0:
      d.append(i)
      t.append(i)
      c+=1
  while d:
    i=d.popleft()
    for j in e[i]:
      x[j]-=1
      if x[j]==0:
        d.append(j)
        t.append(j)
        c+=1
  return t
d=find_loop(n*n,edge)
if len(d)!=n*n:exit(print(-1))
c=[1]*n*n
for i in d:
  for j in edge[i]:
    c[j]=c[i]+1
print(max(c))

### FIXED CODE ###

#閉路判定
#n=頂点数 e=隣接リスト
#flag=0...DAG判定　flag=1...トポロジカルソート
from collections import deque
def find_loop(n,e,flag):
  x=[0]*n
  d=deque()
  t=[]
  c=0
  for i in range(n):
    for j in edge[i]:x[j]+=1
  for i in range(n):
    if x[i]==0:
      d.append(i)
      t.append(i)
      c+=1
  while d:
    i=d.popleft()
    for j in edge[i]:
      x[j]-=1
      if x[j]==0:
        d.append(j)
        t.append(j)
        c+=1
  if flag==0:return c==n
  else:return t

n=int(input())
edge=[[]for _ in range(n*n)]
inp=[1]*n*n
p=lambda x,y:min(x,y)*n+max(x,y)
for i in range(n):
  a=list(map(int,input().split()))
  for j in range(1,n-1):
    edge[p(i,a[j-1]-1)].append(p(i,a[j]-1))
if find_loop(n*n,edge,0)==False:print(-1);exit()
t=find_loop(n*n,edge,1)
ans=[1]*n*n
for i in t:
  for j in edge[i]:ans[j]=max(ans[j],ans[i]+1)
print(max(ans))
### BUGGY CODE ###

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

mod = 10**9 + 7 

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

a = (2*X-Y)//3
b = (2*Y-X)//3

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
# mod = 10**9+7 #出力の制限
N = 10**6+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
 
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    # inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    # g2.append( (g2[-1] * inverse[-1]) % mod )
    g2.append( pow(g1[-1],mod-2,mod) )


print(cmb(a+b,a,mod))

### FIXED CODE ###

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

mod = 10**9 + 7 

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

a = (2*X-Y)//3
b = (2*Y-X)//3

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
# mod = 10**9+7 #出力の制限
N = 10**6+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
 
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

print(cmb(a+b,a,mod))