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

from time import*
from fractions import*
start=time()
M=10**9+7
lcm=lambda x,y:x//gcd(x,y)*y
n,*a=map(int,open(0).read().split())
if n==1:
    print(1)
    exit()
s=a[0]
for t in a[1:]:
    if time()-start>1:
        s*=t
    else:
        s=lcm(s,t)
c=0
for i in a:
    c+=s//i
    c%=M
print(c)

### FIXED CODE ###

from fractions import*
from functools import*
M=10**9+7
_,a=open(0)
*a,=map(int,a.split())
s=reduce(lambda x,y:x//gcd(x,y)*y,a)%M
c=0
for i in a:
    c+=s*pow(i,M-2,M)
    c%=M
print(c)
### BUGGY CODE ###

import collections
S=input()
src=[10**n*int(S[-(n+1)]) for n in range(len(S))]
sumS=[0]
for s in range(len(src)):
  sumS.append((sumS[s]+src[s])%2019)
sumS=sumS[1:]
ans=0
s=collections.Counter(sumS)

for n in s.values():
  ans+=n*(n-1)//2
print(ans+s[0])

### FIXED CODE ###

S=input()
N=len(S)

a=0
t=1
d=[0]*2019
d[0]=1
for i in range(N):
  a+=int(S[N-1-i])*t
  a%=2019
  t*=10
  t%=2019
  d[a]+=1

ans=0
for n in d:
  ans += n*(n-1)//2
print(ans)
### BUGGY CODE ###

s=input()
a=int(input())

for i in range(a):
    c=input()
    if c[0]=='1':
        s=''.join(list(reversed(s)))
    else:
        if c[2]=='1':
            s=c[4]+s
        else:
            s=s+c[4]
            
print(s)

### FIXED CODE ###

s=input()
n=int(input())
rev=1
pre=''
suf=''

for i in range(n):
  q=input().split()
  if q[0]=='1':
    rev+=1
  elif (rev+int(q[1]))%2==0:
    pre=q[2]+pre
  else:
    suf=suf+q[2]
    
ans=pre+s+suf
  
if rev%2==0:
  print(ans[::-1])
else:
  print(ans)
### BUGGY CODE ###

n,m = map(int , raw_input().split())
x = map(int, raw_input().split())
y = map(int, raw_input().split())

sum = 0

for i in range(n-1):
    for j in range(n):
        for k in range(n):
            if j-k == i+1:
                for p in range(m-1):
                    for q in range(m):
                        for r in range(m):
                            if q-r == p+1:
                                sum += (x[j]-x[k])*(y[q]-y[r])
print sum % (10**9+7)

### FIXED CODE ###

import numpy as np
n,m = map(int , raw_input().split())
x = map(int, raw_input().split())
y = map(int, raw_input().split())

sum_x = 0
sum_y = 0

for i in range(n):
    sum_x += i*x[i]-(n-i-1)*x[i]
for i in range(m):
    sum_y += i*y[i]-(m-i-1)*y[i]
print (sum_x*sum_y) % (10**9+7)
### BUGGY CODE ###

# 頂点 v の所属するグループを調べる
def root(v, uni):
  if uni[v] < 0:  # v が親の場合
    return v
  else:           # v が子の場合
    uni[v] = root(uni[v], uni)  # 親のrootを調べる
    return uni[v]

# 頂点 a と頂点 b をつなぐ。もともと同じグループのとき、False を返す
def connect(a, b, uni):
  # まずはそれぞれ根の番号に置き換える
  ra = root(a, uni)
  rb = root(b, uni)
  if ra == rb:  # a と b がそもそも同じグループに属しているなら即終了
    return False
  
  # ra と rb を結合し、rb の親を ra とする
  uni[rb] = ra
  return True


##
N, K, L = map(int, input().split())

road = [0]*(N+1)
rail = [0]*(N+1)

for i in range(1, N+1):
  road[i] = -i
  rail[i] = -i

for i in range(K):
  a, b = map(int, input().split())
  connect(a, b, road)

for i in range(L):
  a, b = map(int, input().split())
  connect(a, b, rail)


##
dp = [0]*(N+1)
for i in range(1, N+1):
  dp[i] = (root(i, road), root(i, rail))

dic = {}
for i in range(1, N+1):
  key = dp[i]
  if key not in dic:
    dic[key] = 1
  else:
    dic[key] += 1

ans = ""
for i in range(1, N+1):
  tmp = dic[dp[i]]
  if i == 1:
    ans = str(tmp)
  else:
    ans += " " + str(tmp)
print(ans)


### FIXED CODE ###

# 頂点 v の所属するグループを調べる
def root(v, uni):
  if uni[v] < 0:  # v が親の場合
    return v
  else:           # v が子の場合
    uni[v] = root(uni[v], uni)  # 親のrootを調べる
    return uni[v]

# 頂点 a と頂点 b をつなぐ。もともと同じグループのとき、False を返す
def connect(a, b, uni):
  # まずはそれぞれ根の番号に置き換える
  ra = root(a, uni)
  rb = root(b, uni)
  if ra == rb:  # a と b がそもそも同じグループに属しているなら即終了
    return False
	
  # ra を大きなグループにしたいので、逆であれば入れ替える
  if uni[ra] > uni[rb]: # rbの方が要素数が多ければ
    tmp = ra
    ra  = rb 
    rb  = tmp

  # ra と rb を結合し、rb の親を ra とする
  uni[ra] += uni[rb]
  uni[rb] = ra
  return True
      
##
N, K, L = map(int, input().split())

road = [-1]*(N+1)
rail = [-1]*(N+1)

for i in range(K):
  a, b = map(int, input().split())
  connect(a, b, road)

for i in range(L):
  a, b = map(int, input().split())
  connect(a, b, rail)


##
dp = [0]*(N+1)
for i in range(1, N+1):
  dp[i] = (root(i, road), root(i, rail))

dic = {}
for i in range(1, N+1):
  key = dp[i]
  if key not in dic:
    dic[key] = 1
  else:
    dic[key] += 1

for i in range(1, N+1):
  ans = dic[dp[i]]
  if i == N:
    print(ans)
  else:
    print(ans, end=" ")
### BUGGY CODE ###


# coding: utf-8

# In[1]:

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


# In[2]:

import copy
import numpy as np


# In[3]:

try:
    from math import gcd as ogcd
except:
    from fractions import gcd as ogcd
from functools import reduce

def gcd(*numbers):
    return reduce(ogcd, numbers)


# In[4]:

gcd_list = []
for i in range(N):
    Ac = copy.copy(A)
    Ac.pop(i)
    #print(Ac)
    gcd_list.append(gcd(*Ac))


# In[5]:

print(np.max(np.array(gcd_list)))


# In[ ]:





### FIXED CODE ###


# coding: utf-8

# In[1]:

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


# In[2]:

#import copy
#import numpy as np
try:
    from fractions import gcd
except:
    from math import gcd


# In[ ]:

# 左からn個の最大公約数を求める O(n)
# 右からn個の最大公約数を求める O(n)
# n個目を抜いた最大公約数は n-1個目までの公約数とn+1個目からの公約数との公約数


# In[3]:

lg = [1]*(N)
rg = [1]*(N)
ans = 0


# In[4]:

#print(lg)
#print(rg)
#print(A)


# In[5]:

lg[0] = A[1]
rg[0] = A[N-2]
lg[1] = A[0]
rg[1] = A[N-1]
#print(lg, rg)
for i in range(1, N-1):
    #print(i)
    lg[i+1] = gcd(lg[i], A[i])
    #print(lg[i], A[i])
    rg[i+1] = gcd(rg[i], A[N-1-i])
    #print(rg[N-1-i], A[N-1-i])
#print(lg, rg)

for i in range(N):
    #print(i, lg[i], rg[N-i-1])
    tmp = gcd(lg[i], rg[N-i-1])
    #print(tmp)
    if ans < tmp:
        ans = tmp
    #print(ans)


# In[6]:

print(ans)


# In[ ]:

"""
[42 54 69 92 12 23]のとき
 1 [54 69 92 12 23]の最大公約数
 2 [42 69 92 12 23]
 3 [42 54 92 12 23]
 4 [42 54 69 12 23]

"""
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]
b = [0 for _ in range(len(a))]

maxnum = len(a) + 1
ans = ""
anscount = 0
for i in range(len(a)-1, -1, -1):
  mod = a[i]
  now = i + 1
  count = 1
  truemod = 0
  while (True):
    if now * count < maxnum:
      truemod += b[now*count-1]
      count += 1
    else:
      break
  if truemod % 2 != mod:
    b[i] = 1
    anscount += 1
    ans += str(i+1)+ " "
print(anscount)
if anscount > 0:
  print(ans[:-1])

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
b = [0 for _ in range(len(a))]

ans = ""
anscount = 0
for i in range(n-1, -1, -1):
  ai = a[i]
  j = i + 1
  while i < n:
    if b[i]:
      ai ^= 1
    i += j
    b[j-1] = ai
res = []
for i, one in enumerate(b):
  if one==1:
    res.append(i+1)
print(len(res))
print(*res)
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
c,d,s = [0 for _ in range(n+1)],[0 for _ in range(n+1)],[0 for _ in range(n+1)]
for i in A:
    c[i] += 1
    d[c[i]] += 1
for i in range(1,n+1):
    s[i] = s[i-1]+d[i]
for i in range(1,n+1):
    l,u = 0,n+1
    while u-l > 1:
        mid = (l+u)//2
        if s[mid] >= i*mid:
            l = mid
        else:
            u = mid
    print(l)

### FIXED CODE ###

N = int(input())
 
A = list(map(int,input().split()))
 
dic = {}
 
for a in A:
 
    if a not in dic:
        dic[a] = 1
    else:
        dic[a] += 1
 
B = []
for i in dic:
    B.append(dic[i])
 
B.sort()
 
B_sub = B.copy()
 
for i in range(len(B)-1):
    B_sub[i+1] += B_sub[i] 
 
aind = N + 1
nind = len(B) - 1
 
#print (B,B_sub)
 
for i in range(N):
 
    i += 1
 
    while True:
 
        while nind > 0 and B[nind] > aind - 1:
 
          nind -= 1
 
        if i > len(B):
            print (0)
            break
 
        elif ((len(B) - 1) - nind ) * (aind-1) + B_sub[nind] >= (aind - 1) * i:
            print (aind - 1)
            break
 
        aind -= 1
### BUGGY CODE ###

N, M = map(int, input().split())
ab = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1 or b == N:
        ab.append([int(a), int(b)])

flag = False
for i in range(len(ab)):
    for k in range(len(ab)-i):
        if ab[i][1] == ab[-k][0] or ab[i][0]==ab[-k][1]:
            print('POSSIBLE')
            flag = True
            break
    if flag:
        break
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

#真に大切なのは中間点となる要素
N, M = map(int, input().split())
an = set()
nb = set()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        an.add(b)
    elif b == N:
        nb.add(a)

print('IMPOSSIBLE' if len(an&nb)==0 else 'POSSIBLE')
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [10**9] * N

dp[0] = 0
for i in range(1, N):
    step = K+1 if K < i else i+1
    for j in range(1, step):
        dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))
        
print(dp[N-1])


### FIXED CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]

INF = float('inf')
dp = [INF] * N
dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2, N):
    tmp = INF
    step = max(0, i-K)
    for j in range(step, i):
        tmp = min(tmp, dp[j] + abs(h[i] - h[j]))
    dp[i] = tmp

print(dp[N-1])
### BUGGY CODE ###

z=10
m=z**9+7
k=13
t=input()[::-1]
dp=[0]*k
dp[0]=1
for d in range(len(t)):
  p=[0]*k
  f=(t[d]=='?')
  for i in range(k):
    for x in range(z if f else 1):
      r=pow(z,d,k)
      r*=int(x) if f else int(t[d])
      p[(i+r)%k]+=dp[i]
  dp=[j%m for j in p]
print(dp[5]%m)

### FIXED CODE ###

from heapq import heappush, heappop
from collections import deque
import itertools
from itertools import permutations
import sys
import bisect
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
mo=10**9+7
imp='IMPOSSIBLE'


s=input()
t=list(s)[::-1]
ans=0
dp=[0]*13
dp[0]=1
for d in range(len(t)):
    
    if t[d]=='?':
        tm=[0]*13
        for x in range(10):
            r=int(x)*pow(10,d,13)
            for i in range(13):
                tm[(i+r)%13]+=dp[i]
        dp=[j%mo for j in tm]
    else:
        tm=[0]*13
        r=int(t[d])*pow(10,d,13)
        for i in range(13):
            tm[(i+r)%13]=dp[i]
        dp=[j for j in tm]
    #print(dp)

print(dp[5]%mo)
### BUGGY CODE ###

def d_practical_skill_test(H, W, D, A, Q, I):
    import numpy
    a = numpy.array(A)
    tmp = []
    for i in range(D):
        i += 1 + D
        t = [0]
        while i <= H * W:
            j, k = numpy.where(a == i)
            l, m = numpy.where(a == i - D)
            j, k = j[0], k[0]
            l, m = l[0], m[0]
            t.append(t[-1] + abs(j - l) + abs(k - m))
            i += D
        tmp.append(t)
    ans=''
    for l, r in I:
        l = l - 1
        r = r - 1
        start = l % D
        ans += str(tmp[start][r // D] - tmp[start][l // D]) + '\n'
    return ans[:-1]

H,W,D = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(H)]
Q = int(input())
I = [[int(i) for i in input().split()] for j in range(Q)]
print(d_practical_skill_test(H, W, D, A, Q, I))

### FIXED CODE ###

def d_practical_skill_test(H, W, D, A, Q, I):
    # クエリが1-indexedなため、配列もそれに従う
    px = [0 for _ in range(H * W + 1)]
    py = [0 for _ in range(H * W + 1)]  # (px[i],py[j])にAijの値が入っている
    d = [0 for _ in range(H * W + 1)]
    for i in range(H):
        for j in range(W):
            px[A[i][j]] = i
            py[A[i][j]] = j
    for i in range(D + 1, H * W + 1):
        d[i] = d[i - D] + abs(px[i] - px[i - D]) + abs(py[i] - py[i - D])
    ans = []
    for l, r in I:
        ans.append(str(d[r] - d[l]))
    return '\n'.join(ans)

H,W,D = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(H)]
Q = int(input())
I = [[int(i) for i in input().split()] for j in range(Q)]
print(d_practical_skill_test(H, W, D, A, Q, I))
### BUGGY CODE ###

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

ans = A[0]

for i in range(1,N):
  ans *= A[i]

if ans > 10 ** 18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

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

if 0 in A:
  print(0)
  exit()

ans = A[0]

for i in range(1,N):
  ans *= A[i]
  if ans > 10 ** 18:
    print(-1)
    exit()

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

mod = 10 ** 9 + 7

class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

def main():
    K = int(input())
    S = input()

    N = len(S)
    mc = ModComb(N + K + 10)

    ans = 0
    for i in range(K + 1):
        ans += pow(25, i, mod) * pow(26, K - i, mod) * mc.nCk(i + N - 1, N - 1)
        ans %= mod

    print(ans)

main()

### FIXED CODE ###

mod = 10 ** 9 + 7

class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

K = int(input())
S = input()

N = len(S)
mc = ModComb(N + K + 10)

ans = 0
for i in range(K + 1):
    ans += pow(25, i, mod) * pow(26, K - i, mod) * mc.nCk(i + N - 1, N - 1)
    ans %= mod

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

# -*- coding: utf-8 -*-
import numpy

# スペース区切りの整数の入力
A,B = map(int, input().split())

ans = A

for i in range(A+1,B+1,1):
  ans=ans^i
  
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy

# スペース区切りの整数の入力
A,B = map(int, input().split())

num = B-A+1

if A%2==0:
  if num%4==0:
    print("0")
  elif num%4==1:
    print(B)
  elif num%4==2:
    print("1")
  else: #num%4==3:
    print(B^1)
else:
  if num%4==0:
    print(A^B^1)
  elif num%4==1:
    print(A)
  elif num%4==2:
    print(A^B)
  else: #num%4==3:
    print(A^1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N = ii()
S = [sorted(li()) for _ in range(3)]
rec = [[0]*N for i in range(2)]

for i in range(N):
    for j in range(2):
        rec[j][i] = bisect.bisect_right(S[j+1], S[j][i])

ans = 0
for i in range(N):
    for j in range(rec[0][i], N):
        ans += N - rec[1][j]

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
from itertools import accumulate #list(accumulate(A))

N = ii()
S = [sorted(li()) for _ in range(3)]
rec = [[0]*N for i in range(3)]

for i in range(N):
    #for j in range(2):
    #rec[0][i] = bisect.bisect_right(S[1], S[0][i])
    rec[1][i] = N - bisect.bisect_right(S[2], S[1][i])

acc = list(accumulate(rec[1]))
#acc_1 = [0] * N
#for i in range(N):
    #ind = bisect.bisect_right(S[2], acc_

ans = 0
for i in range(N):
    #for j in range(rec[0][i], N):
    ind = bisect.bisect_right(S[1], S[0][i])
    if ind == 0:
        ans += acc[-1]
    else:
        ans += acc[-1] - acc[ind-1]

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

def function(p, i):
  a = p[i]
  amin = min(p[:i+1])
  if amin == a:
    return 1
  else:
    return 0
 
n = int(input())
p = list(map(lambda x: int(x), input().split()))
sums = sum([function(p,i) for i in range(n)])
print(sums)

### FIXED CODE ###

n = int(input())
p = list(map(lambda x: int(x), input().split()))
 
count = 0
maxs = p[0]
for i in range(n):
  if maxs >= p[i]:
    maxs = p[i]
    count += 1
print(count)
### BUGGY CODE ###

import math
from functools import reduce
from collections import deque, Counter
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def prime_factorize(n):
    """
    素因数分解
    
    Sample:
        prime_factorize(36)
        => [2, 2, 3, 3]

        collections.Counter(prime_factorize(36))
        => {2:2, 3:2}
    """
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

    if len(arr) == 0:
        arr.append((n, 1))
    return arr

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]

INF = 999999999999999999999999
MOD = 10**9+7

n,*A = get_all_int()
C = Counter(A)
# log(C)

ans = 0

for i,a in enumerate(A):
    div = make_divisors(a)
    ok = True
    for d in div:
        if d == a:
            if C[d] > 1:
                # log(C[d])
                ok = False
                break
        elif d in C:
            ok = False
            break
    if ok:
        ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter
import sys

def input():
    return sys.stdin.readline().strip()

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            yield i
            if i != n // i:
                yield n//i
        i += 1

n,*A = get_all_int()
A.sort()



C = dict(Counter(A))
keys = C.keys()
# log(C)

checks = [False] * (1000009)

B = []
for i,a in enumerate(A):
    if C[a] == 1:
        B.append(a)
    elif not checks[a]:
        for j in range(a, 1000009, a):
            checks[j] = True

# log(B)

ans = 0

for i,a in enumerate(B):
    if not checks[a]:
        ans += 1
        for j in range(a, 1000009, a):
            checks[j] = True

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

N, M = map(int, (input().split()))
L = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    L[a - 1][b - 1] = 1
    L[b - 1][a - 1] = 1
#print(L)
for i in range(N):
    if L[0][i] == 1:
        if L[i][N - 1] == 1:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")


### FIXED CODE ###

N, M = map(int, (input().split()))
L1 = [0 for i in range(N)]
L2 = [0 for j in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        L1[b - 1] = 1
    elif b == N:
        L2[a - 1] = 1
for i in range(N):
    if L1[i] == L2[i] == 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

N, K = list(map(int, input().split()))
M = abs(N - K)
mini = M

if (N%K == 0):
    print(0)
else:
    while (not M > mini):
        mini = min(mini, M)
        M = abs(M - K)
    print(mini)


### FIXED CODE ###

N, K = list(map(int, input().split()))
M = abs(N - K)
mini = M + 1

if (not N < K):
    if (N%K == 0):
        print(0)
    else:
        M = (N % K)
        while (M < mini):
            mini = min(mini, M)
            M = abs(M - K)
        print(mini)

else:
    while (M < mini):
        mini = min(mini, M)
        M = abs(M - K)
    print(mini)
### BUGGY CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit


@njit
def loof(a):
    N = len(a)
    M = np.zeros(2019,dtype=np.int16)
    M[0] += 1
    T = 0
    memo = pow_mod(10,N,2019)
    for i in range(N-1,-1,-1):
        T = a[i] * memo[N-i-1] + T
        m = T % 2019
        M[m] += 1
        # print(m)
    return M


@njit
def pow_mod(a,n,mod):
    memo = np.array([1])
    if n >= 1:
        for i in range(n-1):
            memo = np.append(memo,memo[-1]*a%mod)
        return memo


def main():
    S = input().rstrip()
    S = list(map(int,list(S)))
    a = np.array(S)

    M = loof(a)
    # print(M)

    res = 0
    ans = np.array([res])

    flag = True
    cnt = 0

    for m in M:
        res += m * (m-1) // 2
        ans = np.append(ans,res)
        if (res == 3) & (flag):
            # print(m,cnt)
            flag = False
        cnt += 1

    # print(M[1164:1167])
    # print(ans)
    print(res)


# print(S)

# np.set_printoptions(threshold=2030)
main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit, i8


# @njit(i8[:](i8,i8,i8[:]))
@njit
def loof(a,N):
    M = np.zeros(2019,dtype=np.int16)
    M[0] += 1
    T = 0
    r = 1
    T += a[-1] * r
    T %= 2019
    M[T] += 1
    for i in range(N-2,-1,-1):
        r *= 10
        r %= 2019
        T += a[i] * r
        T %= 2019
        M[T] += 1
    return M


# @njit
# def pow_mod(a,n,mod):
#     memo = np.array([1])
#     if n >= 1:
#         for i in range(n-1):
#             memo = np.append(memo,memo[-1]*a%mod)
#         return memo
#     else:
#         return memo[0]


def main():
    S = input().rstrip()
    S = list(map(int,list(S)))
    a = np.array(S)

    N = len(a)

    # memo = pow_mod(10,N,2019)
    M = loof(a,N)

    res = 0

    for m in M:
        res += m * (m-1) // 2

    print(res)


main()
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if S[i] == S[j] or S[j] == S[k] or S[k] == S[i]:
                continue
            elif j-i == k-j:
                continue
            else:
                ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R")*S.count("G")*S.count("B")

for i in range(N-2):
    for j in range(i+1,N-1):
        k = 2*j-i
        if k >= N:
            break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            ans -= 1
print(ans)