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

import sys
import copy
n = int(input())
dist = [list(map(int,input().split())) for _ in range(n)]
e = copy.deepcopy(dist)
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j]>dist[i][k] + dist[k][j]:
                print(-1)
                sys.exit()
            if dist[i][j]==dist[i][k] + dist[k][j] and i!=j and i!=k and j!=k:
                #print(i,j,k)
                e[i][j]=float("inf")

#[print(*dist[l]) for l in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j]!=float("inf"):
            ans += dist[i][j]
print(ans//2)

### FIXED CODE ###

import sys
import copy
n = int(input())
dist = [list(map(int,input().split())) for _ in range(n)]
e = copy.deepcopy(dist)
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j]>dist[i][k] + dist[k][j]:
                print(-1)
                sys.exit()
            if i!=j and i!=k and j!=k and dist[i][j]==dist[i][k] + dist[k][j]:
                #print(i,j,k)
                e[i][j]=float("inf")

#[print(*dist[l]) for l in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j]!=float("inf"):
            ans += dist[i][j]
print(ans//2)
### BUGGY CODE ###

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

def yakusuu(p):
	A.reverse()
	for i in range(1,p):
		if A[0] % A[i] == 0:
			A.pop(0)
			return
	else:
		return
def syou(k):
	A.sort()
	if A[0] == 0:
		A.pop(0)
		if len(A) > 1:
			A[k-1] = A[k-1] % A[0]
	else:
		A[k] = A[k] % A[0]
	return A
for i in range(N):
	if len(A) >= 1:
		yakusuu(len(A))
while	len(A) > 1:
	syou(len(A)-1)
print(A[0])

### FIXED CODE ###

import fractions
from functools import reduce
N = int(input())
A = input().split()
A = [int(i) for i in A]
print(reduce(fractions.gcd,A))
### BUGGY CODE ###

from sys import stdin, stderr

def rec(A, i, m):
    if i == 0:
        return m == 0 or A[i] == m

    return rec(A, i - 1, m) or rec(A, i - 1, m - A[i])

n = int(input())
A = [int(i) for i in input().split()]
q = int(input())
M = [int(i) for i in input().split()]

for m in M:
    if rec(A, n - 1, m):
        print('yes')
    else:
        print('no')

### FIXED CODE ###

def solve():
    def dfs(idx, end, value, is_make):
        if idx == end:
            if value > 2000:
                return
            
            is_make[value] = True
            return

        dfs(idx + 1, end, value + A[idx], is_make)
        dfs(idx + 1, end, value, is_make)

    n = int(input())
    A = [int(i) for i in input().split()]
    q = int(input())
    M = [int(i) for i in input().split()]

    is_make = [False] * (2000 + 1)
    dfs(0, n, 0, is_make)

    for m in M:
        print('yes' if is_make[m] else 'no')

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

N, M = tuple(map(int, input().split()))
mod = 10**9+7
broken = [int(input()) for _ in range(M)]
dp = [0]* (N+1)


dp[0] = 1

for i in range(1, N+1):
    if (i in broken):
        continue
    if (i == 1):
        dp[i] = 1
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[N])

### FIXED CODE ###

N, M = map(int, input().split())
A = set(int(input()) for _ in range(M))
mod = 10 ** 9 + 7

dp = [0] * (N+1)
dp[0] = 1
for i in range(1, N+1):
    if i in A:
        continue
    if i == 1:
        dp[i] = 1
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= mod

print(dp[N] % mod)
### BUGGY CODE ###

n = int(input())
tli = [ int(it) for it in input().split() ]
ali = [ int(it) for it in input().split() ]
#print (tli,ali)

mav1 = max(tli)
mav2 = max(ali)
mav = mav1
#print (mav1,mav2)
if (mav1!=mav2):
  print (0)
else:
  mai1 = tli.index(mav)
  mai2 = n-1-list(reversed(ali)).index(mav)
  #print (mai1,mai2)
  if (mai2<mai1):
    print (0)
  else:
    s = 1
    tma = -1
    for i in range(0,mai1+1):
      if tli[i]>tma:
        tma = tli[i]
        #print ("lt",tma)
      else:
        s*=(tli[i])
        #print ("l")
    tma = -1
    for i in range(n-1,mai2-1,-1):
      if ali[i]>tma:
        tma = ali[i]
        #print ("rt",tma)
      else:
        s*=(ali[i])
        #print ("r")
    if (mai2-mai1>1):
      for i in range(mai2-mai1-1):
        s*=mav
    print ( s%(1000000007) )
      
    
        
    
 

### FIXED CODE ###

MOD = 1000000007
n = int(input())
tli = [ int(it) for it in input().split() ]
ali = [ int(it) for it in input().split() ]
#print (tli,ali)

mav1 = max(tli)
mav2 = max(ali)
mav = mav1
#print (mav1,mav2)
if (mav1!=mav2):
  print (0)
else:
  mai1 = tli.index(mav)
  mai2 = n-1-list(reversed(ali)).index(mav)
  #print (mai1,mai2)
  if (mai2<mai1):
    print (0)
  else:
    s = 1
    tma = -1
    for i in range(0,mai1+1):
      if tli[i]>tma:
        tma = tli[i]
        #print ("lt",tma)
      else:
        s*=(tli[i])
        s%=MOD
        #print ("l")
    tma = -1
    for i in range(n-1,mai2-1,-1):
      if ali[i]>tma:
        tma = ali[i]
        #print ("rt",tma)
      else:
        s*=(ali[i])
        s%=MOD
        #print ("r")
    if (mai2-mai1>1):
      for i in range(mai2-mai1-1):
        s*=mav
        s%=MOD
    print ( s%(1000000007) )
### BUGGY CODE ###

s = input()
k = int(input())



rank = []
for i in range(len(s)):
    for j in range(i+1, max(i+6,len(s)+1)):
        ss = s[i:j]
        rank.append(ss)

rank = sorted(list(set(rank)))
print(rank[k-1])


### FIXED CODE ###

s = input()
k = int(input())



rank = []
for i in range(len(s)):
    for j in range(i+1, min(i+6,len(s)+1)):
        ss = s[i:j]
        rank.append(ss)

rank = sorted(list(set(rank)))
print(rank[k-1])
### BUGGY CODE ###

N = int(input())
d = list(map(int,input().split()))
E = []
while len(d)>0:
  a = min(d)
  E.append(a)
  d.remove(a)

k = int(N/2)
print(int(E[k])-int(E[k-1]))

### FIXED CODE ###

N = int(input())
d = list(map(int,input().split()))
d.sort()
n= int(N/2)
print(d[n]-d[n-1])
### BUGGY CODE ###

import sys
import queue
input = sys.stdin.readline
H,W = [int(i) for i in input().split()]
A = []
P = queue.Queue()
check = [[True for _ in range(W)] for _ in range(H)]

for j in range(H):
    a = list(input())
    if '#' in a:
        for i in range(W):
            if a[i] == '#':
                check[j][i] = False
                P.put([j,i])
    A.append(a)

ans = [[0 for _ in range(W)] for _ in range(H)]
count = 0
while not P.empty():
    hNow,wNow = P.get()
    if hNow-1 >= 0:
        if check[hNow-1][wNow]:
            P.put([hNow-1,wNow])
            ans[hNow-1][wNow] = ans[hNow][wNow]+1
            check[hNow-1][wNow] = False
            count = max(count,ans[hNow-1][wNow])

    if hNow+1 < H:
        if check[hNow+1][wNow]:
            P.put([hNow+1,wNow])
            ans[hNow+1][wNow] = ans[hNow][wNow]+1
            check[hNow+1][wNow] = False
            count = max(count,ans[hNow+1][wNow])

    if wNow-1 >= 0:
        if check[hNow][wNow-1]:
            P.put([hNow,wNow-1])
            ans[hNow][wNow-1] = ans[hNow][wNow]+1
            check[hNow][wNow-1] = False
            count = max(count,ans[hNow][wNow-1])

    if wNow+1 < W:
        if check[hNow][wNow+1]:
            P.put([hNow,wNow+1])
            ans[hNow][wNow+1] = ans[hNow][wNow]+1
            check[hNow][wNow+1] = False
            count = max(count,ans[hNow][wNow+1])

print(count)


### FIXED CODE ###

from collections import deque

H,W = [int(i) for i in input().split()]
l = [list(input()) for _ in range(H)]
ans = [[-1]*W for _ in range(H)]
q = deque()

for i in range(H):
    for j in range(W):
        if l[i][j] == '#':
            q.append([i,j])
            ans[i][j] = 0

t = 0
while q:
    i,j = q.popleft()
    for next_i, next_j in [[i+1,j], [i-1,j], [i,j+1], [i,j-1]]:
        if 0 <= next_i < H and 0 <= next_j < W:
            if ans[next_i][next_j] == -1 and l[next_i][next_j] == '.':
                ans[next_i][next_j] = ans[i][j] + 1
                t = max(t, ans[next_i][next_j])
                q.append([next_i,next_j])

print(t)
### BUGGY CODE ###

a,b,c,k = map(int,input().split())
ans = 0

for i in range(k):
  if(a != 0):
    ans += 1
    a -= 1
  elif(b != 0):
    b -= 1
  else:
    ans -= 1
    c -= 1
print(ans)



### FIXED CODE ###

a,b,c,k = map(int,input().split())
ans = 0

if(k > a):
  ans = a
  k = k - a
else:
  ans = k
  k = k - a
if(k > 0):
  k = k - b
if(k > 0):
  ans = ans - k

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

import re
n = int(input().split()[1])
s = input()
for i in range(n):
  l, r = map(int, input().split())
  ma = re.findall('AC', s[l-1: r])
  print(len(ma))

### FIXED CODE ###

import re
n = int(input().split()[1])
s = input()

counts = [0]
for i in range(len(s)):
  counts.append(counts[i] + (1 if s[i : i + 2] == 'AC' else 0))

for i in range(n):
  l, r = map(int, input().split())
  print(counts[r - 1] - counts[l - 1])
### BUGGY CODE ###

def cul_dis(start,goal):
    return abs(start[0]-goal[0])+abs(start[1]-goal[1])

H,W,d = map(int,input().split())
number_pos = {}

for h in range(H) :
    state = list(map(int,input().split()))
    for i,number in enumerate(state):
        number_pos[number] = [h,i]

Q = int(input())

exams = []
for _ in range(Q):
    exams.append(list(map(int,input().split())))

for [L,R] in exams:
    mp = 0
    now_number = L
    while(now_number!=R):
        next_number = now_number+d
        mp += cul_dis(number_pos[now_number],number_pos[next_number])
        now_number = next_number
    print(mp)

### FIXED CODE ###

def cul_dis(start,goal):
    return abs(start[0]-goal[0])+abs(start[1]-goal[1])

H,W,d = map(int,input().split())
number_pos = {}

for h in range(H) :
    state = list(map(int,input().split()))
    for i,number in enumerate(state):
        number_pos[number] = [h,i]

Q = int(input())

exams = []
for _ in range(Q):
    exams.append(list(map(int,input().split())))

mp_consume = [0 for i in range(H*W)]

for i in range(H*W)[::-1]:
    if i+d <= H*W-1:
        mp_consume[i] = mp_consume[i+d]+cul_dis(number_pos[i+1],number_pos[i+d+1])

for [start,goal] in exams:
    ans = mp_consume[start-1]-mp_consume[goal-1]
    print(ans)
### BUGGY CODE ###

import collections
n = int(input())
a = list(map(int,input().split()))
aa = collections.Counter(a)
ans = 0
num = 0
for k in aa.keys():
  num = a.count(k)+a.count(k-1)+a.count(k+1)
  ans = max(ans,num)
print(ans)

### FIXED CODE ###

N = int(input())
a = [int(x) for x in input().split()]
memo = [0]*(10**5+2)
ans = 1
for i in range(N):
  memo[a[i]] += 1
  memo[a[i]+1] += 1
  memo[a[i]-1] += 1
print(max(memo))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

if m==0:
    cnt = 0
    steps = n
    for j in range(steps//2+1):
        if j == 0:
            cnt += 1
        else:
            seat = steps - j
            cnt += combinations_count(seat,j)
    print(cnt % (10**9+7))
    exit()

l = [-1]+[int(input())]
for i in range(m-1):
    a = int(input())
    if a == l[-1]+1:
        print(0)
        exit()
    l.append(a)
l.append(n+1)
# print(l)

ans = 1
for i in range(m+1):
    cnt = 0
    steps = l[i+1] - l[i] -2
    for j in range(steps//2+1):
        if j == 0:
            cnt += 1
        else:
            seat = steps - j
            cnt += combinations_count(seat,j)
    ans *= cnt

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


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

dp = [0]*(n+1)
dp[0] = 1
for i in range(n):
    for j in range(i+1,min(n,i+2)+1):
        if oks[j]:
            dp[j] += dp[i]
            dp[j] %= (10**9+7)
print(dp[n])
### BUGGY CODE ###

def prepare(n, MOD):

    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


k = int(input())
s = input()
length = len(s)
MOD = 10**9 + 7

fact, inv = prepare(k + length, MOD)

ans = 0

for i in range(length, length + k + 1):
    coef = fact[i - 1] * inv[i - length] * inv[length - 1]
    ans += coef * pow(25, i - length, MOD) * pow(26, length + k - i, MOD) % MOD

print(ans % MOD)

### FIXED CODE ###

def solve(k, length, MOD, div, dp):
    for i in range(1, k + 1):
        dp[0] = dp[0] * 25 * div * (length + i - 1) * pow(i, -1, MOD) % MOD
        dp[1] = (dp[1] + dp[0]) % MOD

    return(dp[1])


k = int(input())
s = input()
length = len(s)
MOD = 10**9 + 7
div = pow(26, -1, MOD)

dp = [pow(26, k, MOD)] * 2

print(solve(k, length, MOD, div, dp))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from itertools import accumulate
def solve(k: int, q: int, d: "List[int]", n: "List[int]", x: "List[int]", m: "List[int]"):
    for query in range(q):
        N,X,M = n[query],x[query],m[query]
        count = [0]*k
        D = [0]*k
        c = 0
        for i in range(k):
            D[i] = d[i]%M
            if D[i] == 0:
                c += 1
            count[i] = c
        accum = list(accumulate(D))
        SUMD = accum[-1]
        COUNTD = count[-1]

        if (N-1)%k == 0:
            last = X+((N-1)//k)*SUMD
            equal_count = COUNTD*((N-1)//k)
        else:
            last = X + SUMD*((N-1)//k) + accum[(N-1)%k-1]
            equal_count = COUNTD*((N-1)//k)+count[(N-1)%k-1]
        
        shounari_count = last//M - X//M
        dainari_count = N-shounari_count-equal_count-1
        print(dainari_count)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    k = int(next(tokens))  # type: int
    q = int(next(tokens))  # type: int
    d = [int(next(tokens)) for _ in range(k - 1 - 0 + 1)]  # type: "List[int]"
    n = [int()] * (q)  # type: "List[int]"
    x = [int()] * (q)  # type: "List[int]"
    m = [int()] * (q)  # type: "List[int]"
    for i in range(q):
        n[i] = int(next(tokens))
        x[i] = int(next(tokens))
        m[i] = int(next(tokens))
    solve(k, q, d, n, x, m)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from itertools import accumulate
def solve(k: int, q: int, d: "List[int]", n: "List[int]", x: "List[int]", m: "List[int]"):
    for query in range(q):
        N,X,M = n[query],x[query],m[query]
        count = [0]*k
        D = [0]*k
        c = 0
        for i in range(k):
            D[i] = d[i]%M
            if D[i] == 0:
                c += 1
            count[i] = c
        accum = list(accumulate(D))
        SUMD = accum[-1]
        COUNTD = count[-1]

        if (N-1)%k == 0:
            last = X+((N-1)//k)*SUMD
            equal_count = COUNTD*((N-1)//k)
        else:
            last = X + SUMD*((N-1)//k) + accum[(N-1)%k-1]
            equal_count = COUNTD*((N-1)//k)+count[(N-1)%k-1]
        
        shounari_count = last//M - X//M
        dainari_count = N-shounari_count-equal_count-1
        print(dainari_count)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    k = int(next(tokens))  # type: int
    q = int(next(tokens))  # type: int
    d = [int(next(tokens)) for _ in range(k - 1 - 0 + 1)]  # type: "List[int]"
    n = [int()] * (q)  # type: "List[int]"
    x = [int()] * (q)  # type: "List[int]"
    m = [int()] * (q)  # type: "List[int]"
    for i in range(q):
        n[i] = int(next(tokens))
        x[i] = int(next(tokens))
        m[i] = int(next(tokens))
    solve(k, q, d, n, x, m)

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

def get_next(state, line):
    nex = [0] * len(line)
    for i in range(len(line)):
        if line[i] == 'L':
            nex[i-1] += state[i]
        else:
            nex[i+1] += state[i]
    return nex

def resolve():
    line = input()
    now = [1] * len(line)
    before1 = now
    for i in range(10**100):
        before2 = before1
        before1 = now
        now = get_next(before1, line)
        if before1 == now:
            break
        elif before2 == now:
            if i % 2 == 0:
                now = before1
            break

    now = list(map(str, now))
    print(' '.join(now))

resolve()


### FIXED CODE ###

def resolve():
    line = input()
    result = [0] * len(line)

    r_odd = 0
    r_even = 0
    for i in range(len(line)):
        if line[i] == 'L':
            if i % 2 == 0:
                result[i] += r_even
                result[i-1] += r_odd
            else:
                result[i] += r_odd
                result[i-1] += r_even
            r_odd = 0
            r_even = 0
        elif line[i] == 'R':
            if i % 2 == 0:
                r_even += 1
            else:
                r_odd += 1
    l_odd = 0
    l_even = 0
    for i in range(len(line)-1, -1, -1):
        if line[i] == 'R':
            if i % 2 == 0:
                result[i] += l_even
                result[i+1] += l_odd
            else:
                result[i] += l_odd
                result[i+1] += l_even
            l_odd = 0
            l_even = 0
        elif line[i] == 'L':
            if i % 2 == 0:
                l_even += 1
            else:
                l_odd += 1

    print(*result)
    
resolve()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt=0
for i in range(n-1):
    m=-a[i]
    for k in range(i+1,n):
        m+=1
        if a[k]==m:
            cnt+=1
print(cnt)

### FIXED CODE ###

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

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

for i in range(0, m):
    p, y = list(map(int, input().split()))
    tmps[p-1].append(y)
    pys.append([p, y])

for i in range(n):
    tmps[i] = sorted(tmps[i])

for py in pys:
    p, y = py
    yindex = tmps[p-1].index(y)+1
    print('{:06}'.format(p) + '{:06}'.format(yindex))

### FIXED CODE ###

n, m = list(map(int, input().split()))
tmps = [[] for _ in range(n)]
pyxs = []

for i in range(m):
    p, y = list(map(int, input().split()))
    pyxs.append([p, y, i])

pyxs.sort(key = lambda x: x[1])

num = [0] * (n+1)
ans = [None]*m

for p, y, x in pyxs:
    ans[x] = '{:06}'.format(p) + '{:06}'.format(num[p]+1)
    num[p] += 1

for s in ans:
    print(s)
### BUGGY CODE ###

while True:
    n = int(raw_input())
    if n == 0:
        break
    s = [[] for i in range(n)]
    for i in range(n):
        s[i] = raw_input()
    for i in range(n,0,-1):
        for j in range(n-i+1):
            for k in range(n-i+1):
                flag = 0
                for l in range(i):
                    for m in range(i):
                        if s[j+l][k+m] == "*":
                            flag = 1
                            break
                if flag == 0:
                    print i
                    break
            if flag == 0: break
        if flag == 0: break
    if flag == 1:
        print 0

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0: break
    field = [raw_input() for i in range(n)]
    large = [[0]*(n + 1) for i in range(n + 1)]
    for i in range(n):
        for j in range(n):
            if field[i][j] == '.':
                large[i][j] = min(large[i][j - 1], large[i - 1][j], large[i - 1][j - 1]) + 1
    print max(map(max, large))
### BUGGY CODE ###

import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


s = 'abcdefghijklmnop'
N = I()
s = s[:N]

from itertools import product
seen = set()
for x in product(s,repeat=N):
    d = dict()
    pat = ''
    i = 1
    for n in x:
        if d.get(n) is None:
            d[n] = str(i)
            pat += str(i)
            i += 1
        else:
            pat += d[n]
    if pat in seen:
        continue
    print(''.join(x))
    seen.add(pat)

### FIXED CODE ###

import sys


def I(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LMI(): return list(map(int, sys.stdin.readline().split()))


MOD = 10 ** 9 + 7

s = 'abcdefghijklmnop'
N = I()

for c1 in range(1):
    if N == 1:
        print(s[c1])
        continue
    for c2 in range(2):
        if N == 2:
            print(s[c1]+s[c2])
            continue
        for c3 in range(max(c1, c2) + 2):
            if N == 3:
                print(s[c1] + s[c2] + s[c3])
                continue
            for c4 in range(max(c1, c2, c3) + 2):
                if N == 4:
                    print(s[c1] + s[c2] + s[c3] + s[c4])
                    continue
                for c5 in range(max(c1, c2, c3, c4) + 2):
                    if N == 5:
                        print(s[c1] + s[c2] + s[c3] + s[c4] + s[c5] )
                        continue
                    for c6 in range(max(c1, c2, c3, c4, c5) + 2):
                        if N == 6:
                            print(s[c1] + s[c2] + s[c3] + s[c4] + s[c5] + s[c6])
                            continue
                        for c7 in range(max(c1, c2, c3, c4, c5, c6) + 2):
                            if N == 7:
                                print(s[c1] + s[c2] + s[c3] + s[c4] + s[c5] + s[c6] + s[c7] )
                                continue
                            for c8 in range(max(c1, c2, c3, c4, c5, c6, c7) + 2):
                                if N == 8:
                                    print(s[c1] + s[c2] + s[c3] + s[c4] + s[c5] + s[c6] + s[c7] + s[c8])
                                    continue
                                for c9 in range(max(c1, c2, c3, c4, c5, c6, c7, c8) + 2):
                                    if N == 9:
                                        print(s[c1]+s[c2]+s[c3]+s[c4]+s[c5]+s[c6]+s[c7]+s[c8]+s[c9])
                                        continue
                                    for c10 in range(max(c1, c2, c3, c4, c5, c6, c7, c8, c9) + 2):
                                        print(s[c1]+s[c2]+s[c3]+s[c4]+s[c5]+s[c6]+s[c7]+s[c8]+s[c9]+s[c10])
### BUGGY CODE ###

a = list(input())
a = [int(s) for s in a]
a = a[::-1]
s = [0]

for i in range(len(a)):
    add = s[i] + a[i] * 10**i
    add = add % 2019
    s.append(add)

#print(s)
ans = 0

for i in range(len(s)):
    for j in range(i+1,len(s)):
        if s[i] == s[j]:
            ans += 1

print(ans)

### FIXED CODE ###

a = input()[::-1]
add = 0
ans = [1] + [0] * 2018
ans_int = 0
d = 1

for i in range(len(a)):
    add = (add + int(a[i]) * d) % 2019
    d = (10 * d) %2019
    ans[add] += 1

for i in range(len(ans)):
    a =((ans[i] - 1) * ans[i]) /2
    ans_int += a

print(int(ans_int))
### BUGGY CODE ###

import math
from functools import reduce

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

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

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

P = 10**9 + 7
N = 1000001
inv_t = [0]+[1]
for i in range(2,N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

n=int(input())
A=[int(i) for i in input().split()]

#kyodai=lcm_list(A)
kyodai=A[0]
for i in range(1,n):
    kyodai=lcm_base(kyodai,A[i])

ans=0

for i in range(n):
    ans+=kyodai*inv_t[A[i]]
    ans=ans%P

print(ans)

### FIXED CODE ###

def gcd(a,b):
    for xx in range(1000001):
        a,b=b,a%b
        if b==0:
            break
    return a

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

P = 10**9 + 7
N = 1000001
inv_t = [0]+[1]
for i in range(2,N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

n=int(input())
A=[int(i) for i in input().split()]

#kyodai=lcm_list(A)
kyodai=A[0]
for i in range(1,n):
    kyodai=lcm_base(kyodai,A[i])

ans=0

for i in range(n):
    ans+=inv_t[A[i]]
    ans=ans%P
ans=ans*kyodai
ans=ans%P

print(ans)