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

import fractions

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

N = int(input())
Ps = list(map(int,input().split(" ")))
MOD = 10 ** 9 + 7
g = 1

for p in Ps:
    g = g* p // fractions.gcd(g, p)
ans = 0
for p in Ps:
    ans += g//p
    ans %= MOD
print(ans)





### FIXED CODE ###

from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)

N = int(input())
Ps = list(map(int,input().split(" ")))
MOD = 10 ** 9 + 7
g = 1
for p in Ps:
    g = lcm(g,p)
ans = 0

print(sum([g // p for p in Ps]) % (10 ** 9 + 7))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())

def bin(start):
    ok=0
    ng=n
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid)
        sys.stdout.flush()
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        if mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
print(0)
start=input()
sys.stdout.flush()
if start=='Vacant':exit()
bin(start)


### FIXED CODE ###

import sys
n=int(input())

def bin(start):
    ok=0
    ng=n
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid)
        sys.stdout.flush()
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        elif mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
print(0)
start=input()
sys.stdout.flush()
if start=='Vacant':exit()
bin(start)
### BUGGY CODE ###

k = int(input())

m = 7%k
ans = 1
jud = True
p = 70%k
while m != 0:
    m = (m + p)%k
    ans += 1
    p = p*10%k
    if p == 0:
        jud = False
        break
if jud:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

k = int(input())

m = 0
for i in range(k):
    m = (m*10 + 7)%k
    if m == 0:
        ans = i + 1
        break

if m == 0:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import math
n,m=[int(i) for i in input().split()]
if(abs(n-m)>1):
    print(0)
    exit()

def is_even(n):
    if(n%2==0):
        return True
    else:
        return False
if(is_even(n) and is_even(m) or not is_even(n) and not is_even(m)):
    print(math.factorial(n)*math.factorial(m)*2)
    exit()
else:
    print(math.factorial(n)*math.factorial(m))
    exit()
# if(is_even(n) and is_even(m)):
#     print(math.factorial(n)*math.factorial(m)*2)
#     exit()
# elif(is_even(n) and not is_even(m)):
#     print(math.factorial(n)*math.factorial(m))
#     exit()
# elif(not is_even(n) and is_even(m)):
#     print(math.factorial(m)*math.factorial(n))
#     exit()
# elif(not is_even(n) and not is_even(m)):
#     print(math.factorial(m)*math.factorial(n)*2)
#     exit()

### FIXED CODE ###

import math
n,m=[int(i) for i in input().split()]
if(abs(n-m)>1):
    print(0)
    exit()

def is_even(n):
    if(n%2==0):
        return True
    else:
        return False
if(is_even(n) and is_even(m) or not is_even(n) and not is_even(m)):
    print(math.factorial(n)*math.factorial(m)*2%(10**9+7))
    exit()
else:
    print(math.factorial(n)*math.factorial(m)%(10**9+7))
    exit()
# if(is_even(n) and is_even(m)):
#     print(math.factorial(n)*math.factorial(m)*2)
#     exit()
# elif(is_even(n) and not is_even(m)):
#     print(math.factorial(n)*math.factorial(m))
#     exit()
# elif(not is_even(n) and is_even(m)):
#     print(math.factorial(m)*math.factorial(n))
#     exit()
# elif(not is_even(n) and not is_even(m)):
#     print(math.factorial(m)*math.factorial(n)*2)
#     exit()
### BUGGY CODE ###

from collections import Counter

def Comb(n,k):
    comb_ans=1
    for i in range(1,k+1):
        comb_ans*=(n-i+1)/i
    comb_ans=int(comb_ans)
    return comb_ans

N=int(input())
A=list(map(int,input().split()))
C=Counter()
C.update(A)
ans=0
L=[0]*N
for i in range(N):
    L[A[i]-1]+=1
for i in range(len(C)):
    ans+=Comb(C.most_common()[i][1],2)
for i in range(N):
    pri=ans
    pri=ans-Comb(L[A[i]-1],2)+Comb(L[A[i]-1]-1,2)
    print(pri)

### FIXED CODE ###

from collections import Counter

def Comb(n,k):
    comb_ans=1
    for i in range(1,k+1):
        comb_ans*=(n-i+1)/i
    comb_ans=int(comb_ans)
    return comb_ans

N=int(input())
A=list(map(int,input().split()))
C=Counter()
C.update(A)
ans=0
L=[0]*N
for i in range(N):
    L[A[i]-1]+=1
Most=C.most_common()
#print(Most)
for i in range(len(C)):
    ans+=Comb(Most[i][1],2)
for i in range(N):
    pri=ans
    pri=ans-L[A[i]-1]+1
    print(pri)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
for i in range(1,n+2):
  if not i in a:
    break
  s = a.index(i)
  a = a[s:]
if i == 1:
  print(-1)
else:
  print(n-i+1)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
h = 0
for i in range(0,n):
  if a[i] != i-h+1:
    h += 1
if h == n:
  print(-1)
else:
  print(h)
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
n=int(input())
ans=0
f=[len(make_divisors(i)) for i in range(1,n+1)]
for i in range(1,n+1):
    ans+=i*f[i-1]
print(ans)


### FIXED CODE ###

n=int(input())

#L=[n//i*(i+n//i*i)//2 for i in range(1,n+1)]
#print(sum(L))
ans=0
#for i in range(1,n+1):
#    for j in range(1,n+1):
#        if i%j==0:
#            ans+=i
#print(ans)
g=lambda x:(x*(n//x)*(n//x+1))//2
print(sum(g(i) for i in range(1,n+1)))
### BUGGY CODE ###

x,y,num = map(int, input().split())
gaiz = []
zen_gaiz = [[] for _ in range(x)]
kaisu = x
for _ in range(num):
    xg,yg = map(int,input().split())
    zen_gaiz[xg-1].append(yg)
    if xg > yg:
        gaiz.append((xg,yg))

if len(gaiz) ==0:
    print(kaisu)
else:
    finish = False
    for gai in sorted(gaiz, key=lambda x: x[0]):
        hidari = [gai[0]-1, gai[1]]
        while True:
            if hidari[1]==1: 
                kaisu = gai[0]-1
                finish=True
                break
            for g in zen_gaiz:
                if hidari[1] in zen_gaiz[hidari[0]-1]:
                    break
            else:
                hidari[0]-=1
                hidari[1]-=1
                continue
            break
        if finish:
            break
    print(kaisu) 
                

### FIXED CODE ###

x,y,num = map(int, input().split())
gaiz = [x]*x
kaisu = x
for _ in range(num):
    xg,yg = map(int,input().split())
    if xg >= yg:
        sa = xg-yg
        if yg < gaiz[sa]:
            gaiz[sa]=(yg)
 
if len(gaiz) ==0:
    print(kaisu)
else:
    for num,(maegai,gai) in enumerate(zip(gaiz[:-1],gaiz[1:])):
        if maegai>gai and num+gai < kaisu:
            kaisu = num+gai
    print(kaisu)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

s = input()
n = int(input())
for i in range(n):
    q = input()
    if len(q) == 1:
        s = s[::-1]
    else:
        _, f, c = q.split()
        if f == '1':
            s = c + s
        else:
            s = s + c
print(s)

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

s = input()
n = int(input())
front = ''
end = ''
front_flag = True # Trueの場合frontがfront Falseの場合endがfront
for i in range(n):
    q = input()
    if len(q) == 1:
        front_flag = not front_flag
    else:
        _, f, c = q.split()
        if f == '1':
            if front_flag:
                front += c
            else:
                end += c
        else:
            if not front_flag:
                front += c
            else:
                end += c

if front_flag:
    s = front[::-1] + s + end
else:
    s = end[::-1] + s[::-1] + front

print(s)
### BUGGY CODE ###

N, M = map(int, input().split())
A = set(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
ans = {0: 0, 1: 0}
for i in range(2, N + 1):
    x = 0
    for j in range(1, 10):
        k = num[j]
        if j not in A or i - k < 0:
            continue
        if i == k:
            x = max(x, j)
            continue
        if i - k in ans:
            an = ans[i - k]
            if an == 0:
                continue
            x = max(x, an * 10 + j)
            x = max(x, j * 10 ** len(str(an)) + an)
    ans[i] = x
print(ans[N])

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [2, 5, 5, 4, 5, 6, 3, 7, 6]
ans = {}
for i in range(N + 1):
    x = 0
    for j in A:
        k = num[j - 1]
        if i - k < 0:
            continue
        if i == k:
            x = max(x, j)
            continue
        an = ans[i - k]
        if an == 0:
            continue
        x = max(x, an * 10 + j)
    ans[i] = x
print(ans[N])
### BUGGY CODE ###

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

s=input()
l=len(s)
i=0
d=0
while i+3<=l-1:
    for j in range(i+3,l):
        if int(s[i:j+1])%2019!=0:
            continue
        else:
            d+=1
            i=i+1
            break
    else:
        i+=1
print(d)




### FIXED CODE ###

from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  k=1
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*k)%2019
      k*=10
      k=k%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

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

N = int(input())
A = []
for _ in range(N):
  A.append(int(input()))

for i in range(N):
  A_ = A.copy()
  A_[i] = 0
  print(max(A_))

### FIXED CODE ###

N = int(input())
max = 0
max2 = 0
n_max = 0
A = []
for _ in range(N):
  a = int(input())
  A.append(a)
  if a > max:
    max2 = max
    max = a
    n_max = 1
  elif a == max:
    n_max += 1
  elif a > max2:
    max2 = a

for a in A:
  if a == max:
    if n_max == 1:
      print(max2)
    else:
      print(max)
  else:
    print(max)
### BUGGY CODE ###

N, M = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]

L = []
R = []
for i in range(M):
  L.append(LR[i][0])
  R.append(LR[i][1])
  
count = 0
flag = 0
for i in range(1, N+1):
  flag = 0
  for j in range(M):
    if not (L[j] <= i <= R[j]):
      break
    else:
      flag += 1
    if flag == M:
      count += 1

print(count)

### FIXED CODE ###

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

LR = [list(map(int, input().split())) for _ in range(M)]

L = []
R = []
for i in LR:
  L.append(i[0])
  R.append(i[1])
  
if min(R) - max(L) < 0:
  print(0)
else:
  print(min(R) - max(L) + 1)
### BUGGY CODE ###

n,x,m = map(int, input().split()) 
ans = 0
x_list = []

for _ in range(n):
    x_list.append(x)
    ans += x
    x = x**2 % m
    if x == 0:
        break
    if x == 1:
        ans = ans + (n-len(x_list))
        break
    if x_list.count(x) == 1:
        after_list = x_list[x_list.index(x):(len(x_list))]
        if x_list.index(x) == 0:
            if (n // len(x_list)) == 0:
                ans = ans * (n // len(x_list))
            else:
                ans = ans * (n // len(x_list)) + sum(x_list[0:((n % len(x_list)))])
        else:
            if (n-x_list.index(x)) % len(after_list) == 0:
                ans = (ans - sum(x_list[0:(x_list.index(x))])) * ((n-x_list.index(x)) // len(after_list)) + sum(x_list[0:(x_list.index(x))])
            else:
                ans = (ans - sum(x_list[0:(x_list.index(x))])) * ((n-x_list.index(x)) // len(after_list)) + sum(after_list[0:(((n-x_list.index(x)) % len(after_list)))]) + sum(x_list[0:(x_list.index(x))])
        break

print(ans)

### FIXED CODE ###

N, X, M = map(int, input().split())
 
def next_f(a):
    return a * a % M
 
visited = [None] * M
sum_at_visit = [None] * M
loop_done = False
 
time = 1
ans = 0
x = X
while time <= N:
    if not loop_done and visited[x] is not None:
        # found cycle                                                                                                                                         
        loop_len = time - visited[x]
        loop_sum = ans + x - sum_at_visit[x]
        loops = (N-loop_len-time) // loop_len
        time += loop_len * loops
        ans += loop_sum * loops
        loop_done = True
    ans += x
    visited[x] = time
    sum_at_visit[x] = ans
    time += 1
    x = next_f(x)
print(ans)
### BUGGY CODE ###

import itertools

X, Y, Z, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

list_ = [a+b+c for (a,b,c) in itertools.product(A, B, C)]
list_.sort(reverse=True)
for N in list_[:K]:
  print(N)

### FIXED CODE ###

import itertools

X, Y, Z, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
 
list_ = [b+c for (b,c) in itertools.product(B, C)]
list_.sort(reverse=True)
 
list__ = [ab+c for (ab,c) in itertools.product(list_[:K], A)]
list__.sort(reverse=True)
for N in list__[:K]:
  print(N)
### BUGGY CODE ###

#!/usr/bin/env python3
# %%
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import itertools
from math import acos, cos, sin

# %%
N, K = map(int, readline().split())
m = map(int, read().split())
XYC = zip(m, m, m)
X, Y, C = zip(*XYC)
Z = [complex(x, y) for x, y in zip(X, Y)]


# %%
def cross_pts(x1, r1, x2, r2):
    D = abs(x1 - x2)
    if r1 + r2 <= D:
        return
    if abs(r1 - r2) >= D:
        return
    theta = acos((r1 * r1 + D * D - r2 * r2) / (2 * r1 * D))
    z = complex(cos(theta), sin(theta)) * r1 / D
    yield x1 + (x2 - x1) * z
    yield x1 + (x2 - x1) * z.conjugate()


# %%
def test(cost):
    R = [cost / c for c in C]

    def gen_y():
        for i in range(N):
            yield Y[i] - R[i]
            yield Y[i] + R[i]
        for i, j in itertools.combinations(range(N), 2):
            for x in cross_pts(Z[i], R[i], Z[j], R[j]):
                yield x.imag
    ys = sorted(gen_y())
    for y1, y2 in zip(ys, ys[1:]):
        y = (y1 + y2) / 2
        event = []
        for i in range(N):
            if R[i] < abs(Y[i] - y):
                continue
            dx = (R[i] ** 2 - (Y[i] - y) ** 2) ** .5
            event.append((X[i] - dx, 1))
            event.append((X[i] + dx, -1))
        event.sort()
        n = 0
        best_n = 0
        for _, dn in event:
            n += dn
            if n > best_n:
                best_n = n
        if best_n >= K:
            return True
    return False


# %%
left = 0
right = 150000
for _ in range(50):
    x = (left + right) / 2
    if test(x):
        right = x
    else:
        left = x
print(right)


### FIXED CODE ###

import sys
from cmath import rect
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

eps = 1e-9

@njit((numba.complex128, numba.float64) * 2, cache=True)
def cross_circles(c1, r1, c2, r2):
    d = abs(c1 - c2)
    if d <= abs(r1 - r2) or r1 + r2 <= d:
        return None
    cos_theta = (r1 * r1 + d * d - r2 * r2) / (2 * r1 * d)
    theta = np.arccos(cos_theta)
    z1 = (c2 - c1) * rect(r1 / d, theta)
    z2 = (c2 - c1) * rect(r1 / d, -theta)
    return (c1 + z1, c1 + z2)

@njit
def test(Z, C, t):
    R = t / C
    cand = list(Z)
    for j in range(len(Z)):
        for i in range(j):
            points = cross_circles(Z[i], R[i], Z[j], R[j])
            if points is not None:
                for p in points:
                    cand.append(p)
    cand = np.array(cand)
    cnt = np.zeros(len(cand), np.int64)
    for i in range(len(Z)):
        cnt += np.abs(cand - Z[i]) <= R[i] + eps
    return np.any(cnt >= K)

N, K = map(int, readline().split())
nums = np.array(read().split(), np.float64)

Z = nums[::3] + 1j * nums[1::3]
C = nums[2::3]

l = 0
r = 10**9
for _ in range(100):
    m = (l + r) / 2
    if test(Z, C, m):
        r = m
    else:
        l = m

print(r)
### BUGGY CODE ###

n = int(input())
tmp = 1
ans = 0
for i in range(1,n+1):
    tmp = tmp*i
print(tmp%(1000000000 + 7))

### FIXED CODE ###

import math
n = int(input())
print(math.factorial(n)%1000000007)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    P = []
    for _ in range(N):
        x, y = map(int, input().split())
        P.append((x, y))

    def calc_dist(pi):
        ret = -1
        reti = -1
        px, py = P[pi]
        for i, (x, y) in enumerate(P):
            d = abs(px - x) + abs(py - y)
            if d > ret:
                ret = d
                reti = i
        return ret, reti

    prev = -2
    ans = -1

    used = {0}
    from random import randrange

    i = 0
    while True:
        ret, i = calc_dist(i)
        if ret == prev:
            ans = ret
            if i in used:
                break
        if prev < ret:
            prev = ret

        if len(used) == N:
            break

        while i in used:
            i = randrange(0, N)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    P = []
    M = []
    for _ in range(N):
        x, y = map(int, input().split())
        P.append(x + y)
        M.append(x - y)
    P.sort()
    M.sort()
    ans = max(P[-1] - P[0], M[-1] - M[0])
    print(ans)


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

# "#"と"."だけで行き来できるエリアを"島"とする
# 島にある"#"から"."には必ず行けるので、
# "#"の数 * "."がその島の場合の数。これをすべて足し合わせる

# visitedになっていない点をすべて捜査する。
# 進めなかった（"#"もしくは"."が連続した）マスはvisitedにしない。

H,W = map(int,input().split())
grid = [None] * H
for i in range(H):
  grid[i] = input()
  
visited = [[False] * W for i in range(H)]

def get_next_unvisited():
  for i in range(H):
    for j in range(W):
      if not visited[i][j]:
        return i,j
  return -1,-1 # 候補なし
  
from collections import deque
ans = 0
cases = ((0,1),(0,-1),(1,0),(-1,0))
while True:
  y,x = get_next_unvisited()
  if y == -1 and x == -1:
    print(ans)
    exit(0)
  # y,x,直前のマス
  q = deque([[y,x,"N"]])
  black = 0
  white = 0
  
  while q:
    y,x,parent = q.popleft()
    if visited[y][x]:
      continue
    point = grid[y][x]
    if point == parent:
      continue
    visited[y][x] = True
    if point == "#":
      black += 1
    if point == ".":
      white += 1
    for c in cases:
      if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
        q.append([y + c[0],x + c[1], point])
  ans += black * white


### FIXED CODE ###

# "#"と"."だけで行き来できるエリアを"島"とする
# 島にある"#"から"."には必ず行けるので、
# "#"の数 * "."がその島の場合の数。これをすべて足し合わせる

# visitedになっていない点をすべて捜査する。
# 進めなかった（"#"もしくは"."が連続した）マスはvisitedにしない。

H,W = map(int,input().split())
grid = [None] * H
for i in range(H):
  grid[i] = input()
  
visited = [[False] * W for i in range(H)]

def get_next_unvisited(checked_y):
  for i in range(checked_y,H):
    for j in range(W):
      if not visited[i][j]:
        return i,j
  return -1,-1 # 候補なし
  
from collections import deque
ans = 0
cases = ((0,1),(0,-1),(1,0),(-1,0))
checked_y = 0
while True:
  y,x = get_next_unvisited(checked_y)
  if y == -1 and x == -1:
    print(ans)
    exit(0)
  checked_y = y
  # y,x,親,親マスの文字
  q = deque([[y,x,-1,-1,"N"]])
  black = 0
  white = 0
  
  while q:
    y,x,parent_y,parent_x,parent = q.pop()
    if visited[y][x]:
      continue
    point = grid[y][x]
    if point == parent:
      continue
    visited[y][x] = True
    if point == "#":
      black += 1
    if point == ".":
      white += 1
    for c in cases:
      if y + c[0] == parent_y and x + c[1] == parent_x:
        continue
      if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
        q.append([y + c[0],x + c[1],y,x, point])
  ans += black * white
### BUGGY CODE ###

N,C = map(int,input().split()) 
XV = [[0,0]] + [[int(i) for i in input().split()] for _ in range(N)] + [[C,0]]

Sum_left = [0] * (N+1)
Sum_right = [0] * (N+1)
for i in range(N):
    Sum_left[i+1] = Sum_left[i] + XV[i+1][1]
    Sum_right[i+1] = Sum_right[i] + XV[N-i][1]

ans = 0
for i in range(N+1):
    for j in range(N+1-i):
        ans = max(ans, Sum_left[i] + Sum_right[j] - XV[i][0] - 2 * (C - XV[N+1-j][0]), Sum_left[i] + Sum_right[j] - 2 * XV[i][0] - (C - XV[N+1-j][0]))

print(ans)

### FIXED CODE ###

N,C = map(int,input().split())
XV = [[0,0]] + [[int(i) for i in input().split()] for _ in range(N)] + [[C,0]]

Sum_left = [0] * (N+1)
Sum_right = [0] * (N+1)
for i in range(N):
    Sum_left[i+1] = Sum_left[i] + XV[i+1][1]
    Sum_right[i+1] = Sum_right[i] + XV[N-i][1]

Sum_right_maxA = [0] * (N+1)
Sum_right_maxB = [0] * (N+1)
for i in range(1,N+1):
    Sum_right_maxA[i] = max(Sum_right_maxA[i-1], Sum_right[i] - 2 * (C - XV[N+1-i][0]))
    Sum_right_maxB[i] = max(Sum_right_maxB[i-1], Sum_right[i] - (C - XV[N+1-i][0]))

ans = 0
for i in range(N+1):
    ans = max(ans, Sum_left[i] + Sum_right_maxA[N-i] - XV[i][0], Sum_left[i] + Sum_right_maxB[N-i] - 2*XV[i][0])
print(ans)
### BUGGY CODE ###

from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, visited, calculated, dp, to):
  if visited[v]:
    if not calculated[v]:
      return -1
    return dp[v]
  visited[v] = True
  dp[v] = 1
  for u in to[v]:
    res = dfs(u, visited, calculated, dp, to)
    if res == -1:
      return -1
    dp[v] = max(dp[v], res + 1)
  calculated[v] = True
  return dp[v]

def toId(i, j, id):
  if i > j:
    i, j = j, i
  return id[i][j]

def main():
  N = int(input())
  a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

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

  visited = [False] * (N * (N - 1) // 2)
  calculated = [False] * (N * (N - 1) // 2)
  dp = [0] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(N):
      if i >= j:
        continue
      id[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  ans = 0
  for i in range(N * (N - 1) // 2):
    res = dfs(i, visited, calculated, dp, to)
    if res == -1:
      print('-1')
      exit()
    ans = max(ans, res)
  print(ans)

main()


### FIXED CODE ###

from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, dp, to):
  t = dp[v]
  if t >= 0:
    return t
  dp[v] = 0
  t = 0
  for u in to[v]:
    res = dfs(u, dp, to)
    if res == 0:
      print('-1')
      exit()
    if res > t:
      t = res
  t += 1
  dp[v] = t
  return t

def toId(i, j, id_db):
  if i < j:
    return id_db[i][j]
  else:
    return id_db[j][i]

def main():
  N = int(input())
  a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

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

  dp = [-1] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(i + 1, N):
      id_db[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id_db)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  print(max(dfs(i, dp, to) for i in range(N * (N - 1) // 2)))

main()
### BUGGY CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, P = lr()
    S = list(map(int, list(sr())))
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += i+1
        print(ans)
        return
    S = S[::-1]
    lp = [0]*P
    c = 0
    for i in range(N):
        d = S[i]*10**i
        c = (c+d)%P
        lp[c] += 1
    ans = lp[0]
    for i in range(P):
        ans += max(lp[i]*(lp[i]-1)//2, 0)
    print(ans)
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, P = lr()
    S = list(map(int, list(sr())))
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += i+1
        print(ans)
        return
    S = S[::-1]
    lp = [0]*P
    c = 0
    for i in range(N):
        d = S[i]*pow(10,i,P)
        c = (c+d)%P
        lp[c] += 1
    ans = lp[0]
    for i in range(P):
        ans += lp[i]*(lp[i]-1)//2
    print(ans)
resolve()