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

import fractions

N = int(input())
A = list(map(int,input().split()))
MOD = 10** 9 + 7
lcm = 1
for a in A:
    lcm = a // fractions.gcd(a,lcm) * lcm

ans = 0
for a in A:
    ans += lcm // a
    ans %= MOD
print(ans)

### FIXED CODE ###

import fractions

N = int(input())
A = list(map(int,input().split()))
MOD = 10** 9 + 7
lcm = 1
for a in A:
    lcm = a // fractions.gcd(a,lcm) * lcm

print(sum(lcm//a for a in A)%MOD)
### BUGGY CODE ###

import copy

N = int(input())
K = list(map(int,input().split()))
"""
N = 4
K = [1, 2 ,3 ,4]
"""
a = list(set(K))
#print(a)
a_count = {}

for i in a :
    a_count[i] = K.count(i)

#print(a_count)

ans_dict = 0
for l in a_count.values() :
        
    ans_dict += l * (l-1)  // 2

#print(ans_dict)

"""
for i in a_count :

    a_count_2 = copy.deepcopy(a_count)
    
    a_count_2[i] -= 1

    #print(a_count_2)
    
    ans_dict[i] = 0
    for l in a_count_2.values() :
        
        ans_dict[i] += l * (l-1)  // 2

#print(ans_dict)
"""

for i in K:
    print(ans_dict - (a_count[i]-1))
    pass

### FIXED CODE ###

import copy
from collections import Counter

N = int(input())
K = list(map(int,input().split()))
"""
N = 4
K = [1, 2 ,3 ,4]
"""
a = list(set(K))
#print(a)
a_count = {}



a_count = Counter(K)
#print(c)

#print(a_count)

ans_dict = 0
for l in a_count.values() :
        
    ans_dict += l * (l-1)  // 2

#print(ans_dict)

"""
for i in a_count :

    a_count_2 = copy.deepcopy(a_count)
    
    a_count_2[i] -= 1

    #print(a_count_2)
    
    ans_dict[i] = 0
    for l in a_count_2.values() :
        
        ans_dict[i] += l * (l-1)  // 2

#print(ans_dict)
"""

for i in K:
    print(ans_dict - (a_count[i]-1))
    pass
### BUGGY CODE ###

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

inf = float('INF')
dp = [inf for i in range(h+1)]
dp[0] = 0
for i in range(n):
    a,b = map(int, input().split())
    for j in range(h+1):
        # print(j+a)
        if j + a <= h and dp[j+a] > dp[j] + b:
            dp[j+a] = dp[j] + b
        elif j + a > h and dp[h] > dp[j] + b:
            dp[h] = dp[j] + b

print(dp[h])
# print(dp)

### FIXED CODE ###

from math import ceil
h,n = map(int,input().split())

inf = float('INF')
dp = [inf for i in range(h+1)]
dp[0] = 0
for _ in range(n):
    a,b = map(int,input().split())
    for i in range(h+1):
        idx = i-a if i >= a else 0
        if i >= a and dp[i] > dp[idx] + b:
            dp[i] = dp[i-a] + b
        elif i <= a and b < dp[i]:
            dp[i] = b
print(dp[h])
# print(dp)
### BUGGY CODE ###

s = str(input())
ans = 0
check = s.count("ABC")
while check > 0:
  ans += check
  s = s.replace("ABC","BCA")
  check = s.count("ABC")
print(ans)

### FIXED CODE ###

s = str(input()).replace("BC", "D")

def f(s):
  ans = 0
  add = 0
  for i in range(len(s)):
    if s[i] == "A":
      add += 1
    if s[i] == "D":
      ans += add
  return ans

ans = 0
j = 0
for i in range(1, len(s)):
  if s[i] == "B" or s[i] == "C":
    ans += f(s[j:i])
    j = i
ans += f(s[j:])

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

import sys
input = sys.stdin.readline

N, L = map(int, input().split())
dic = {}
for _ in range(N):
    s = input().rstrip('\n')
    for i in range(len(s)):
        dic[s[:i+1]] = 1

g = 0
for s in dic.keys():
    t = s[:-1] + str(int(s[-1] == '0'))
    if t not in dic:
        tmp = L - len(s) + 1
        cnt = 0
        while tmp % 2 == 0:
            tmp //= 2
            cnt += 1
        g ^= (2**cnt)

if g:
    print('Alice')
else:
    print('Bob')


### FIXED CODE ###

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

    mod = 10**10+7
    mod2 = 10**10+9
    mod3 = 998244353
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    dic3 = defaultdict(int)
    h_list = []
    h2_list = []
    h3_list = []
    pair = {}
    pair2 = {}
    pair3 = {}
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        h3 = 0
        for i in range(len(s)):
            M += 1
            h = (h*1007 + int(s[i]) + 1) % mod
            pair[h] = (h + 1)%mod if s[i] == '0' else (h-1)%mod
            h2 = (h2 * 2009 + int(s[i]) + 1) % mod2
            pair2[h2] = (h2 + 1)%mod2 if s[i] == '0' else (h2-1)%mod2
            h3 = (h3 * 3001 + int(s[i]) + 1) % mod3
            pair3[h3] = (h3 + 1) % mod3 if s[i] == '0' else (h3 - 1) % mod3
            dic[h] = i+1
            dic2[h2] = i+1
            dic[h3] = i+1
            h_list.append(h)
            h2_list.append(h2)
            h3_list.append(h3)

    g = 0
    seen = defaultdict(int)
    seen2 = defaultdict(int)
    seen3 = defaultdict(int)
    for i in range(M):
        s, s2, s3 = h_list[i], h2_list[i], h3_list[i]
        if seen[s] and seen2[s2] and seen3[s3]:
            continue
        t = pair[s]
        t2 = pair2[s2]
        t3 = pair3[s3]
        if dic[t] == 0 or dic2[t2] == 0 or dic3[t3] == 0:
            p = [dic[s], dic2[s2], dic3[s3]]
            p.sort()
            tmp = L - p[1] + 1
            '''
            if not seen[s]:
                tmp = L - dic[s] + 1
            elif not seen[s2]:
                tmp = L - dic2[s2] + 1
            else:
                tmp = L - dic3[s3] + 1
            '''
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
            #print(g, s, s2, t, t2, dic[t], dic2[t2])
        seen[s] = 1
        seen2[s2] = 1
        seen3[s3] = 1

    if g:
        print('Alice')
    else:
        print('Bob')


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


s=input()
flag=1
length=len(s)
s_flag=[1 for _ in range(length)]
while flag:
    l=sum(s_flag)
    if l<=1:
        break
    comp=0
    while s_flag[comp]==0:
        comp+=1
    # print(s_flag,comp)
    for i in range(comp+1,length):
        if s_flag[i]:
            if s[comp]!=s[i]:
                s_flag[comp]=0
                s_flag[i]=0
                break
            else:
                comp=i
                if i==length-1:
                    flag=0
print(length-sum(s_flag))


### FIXED CODE ###


s=input()
length=len(s)
cnt=[0,0]
for i in range(length):
    if s[i]=='0':
        cnt[0]+=1
    else:
        cnt[1]+=1
print(min(cnt)*2)
### BUGGY CODE ###

import itertools
n = int(input())
l = list(map(int, input().split()))
ll = list(itertools.combinations(l, 3))
ans = 0
for a, b, c in ll:
  if a < b+c and b < c+a and c<a+b:
    ans += 1
print(ans)

### FIXED CODE ###

import bisect
from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
ans = 0

for i in range(n):
  for j in range(n-1, i, -1):
    s = l[i]+l[j]
    ans += bisect_left(l[j+1:n], s)

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

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

v, e = map(int, readline().split())
from collections import defaultdict
g = defaultdict(list)

for _ in range(e):
    s, t = map(int, readline().split())
    g[s].append(t)
    g[t].append(s)
    
visited = set()
lowest = [None] * v
parent = [None] * v
prenum = [None] * v
child = defaultdict(list)
root = 0

# dfs??§tree?????????
stack = [(root, None)]
while stack:
    u, prev = stack.pop()
    if u not in visited:
        parent[u] = prev
        if prev is not None:
            child[prev].append(u)
        visited |= {u}
        prenum[u] = lowest[u] = len(visited)
    
    stack.extend([(v, u) for v in g[u] if v not in visited])
            
leaf = [i for i in range(v) if not child[i]]
for li in leaf:
    while li is not None:
        candidate = [prenum[li]] + [prenum[i] for i in g[li] if i != parent[li]] + [lowest[i] for i in child[li]]
        lowest[li] = min(candidate)
        li = parent[li]

if 2 <= len(child[root]):
    print(root)
for i in range(1, v):
    if child[i] and any(prenum[i] <= lowest[j] for j in child[i]):
        print(i)

### FIXED CODE ###

from sys import stdin
readline = stdin.readline


def main():
    v, e = map(int, readline().split())
    from collections import defaultdict
    g = defaultdict(list)

    for _ in range(e):
        s, t = map(int, readline().split())
        g[s].append(t)
        g[t].append(s)

    visited = set()
    lowest = [None] * v
    parent = [None] * v
    prenum = [None] * v
    child = defaultdict(list)
    root = 0

    # dfs??§tree?????????
    stack = [(root, None)]
    while stack:
        u, prev = stack.pop()
        if u not in visited:
            parent[u] = prev
            if prev is not None:
                child[prev].append(u)
            visited |= {u}
            prenum[u] = lowest[u] = len(visited)

        stack.extend([(v, u) for v in g[u] if v not in visited])

    # lowest????¨????
    from collections import Counter
    leaf = [i for i in range(v) if not child[i]]
    unfinished = Counter()
    for li in leaf:
        while li is not None:
            candidate = [prenum[li]] + [prenum[i] for i in g[li] if i != parent[li]] + [lowest[i] for i in child[li]]
            lowest[li] = min(candidate)
            li = parent[li]
            if li is not None and 1 < len(child[li]):
                unfinished[li] += 1
                if unfinished[li] < len(child[li]):
                    break

    # ??£???????????????
    if 2 <= len(child[root]):
        print(root)
    for i in range(1, v):
        if child[i] and any(prenum[i] <= lowest[j] for j in child[i]):
            print(i)
main()
### BUGGY CODE ###

n,k,q = map(int,input().split())
a = [int(input()) for i in range(q)]

ans = [k]*n
for i in range(q):
  ans = list(map(lambda x : x - 1,ans))
  ans[a[i] - 1] += 1

for i in range(n):
  if ans[i] > 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n,k,q = map(int,input().split())
a = [int(input()) for i in range(q)]

ans = [k-q]*n
for i in range(q):
  ans[a[i] - 1] += 1

for i in range(n):
  if ans[i] > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import heapq
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
AB.sort(key=lambda x:x[0])
AB.append([10**5+1,0])
h=[]
ans=0
for i in range(1,M+1):
  while AB[0][0]<=i:
    heapq.heappush(h,-AB.pop(0)[1])
  if len(h)>0:
    ans+=-heapq.heappop(h)
print(ans)

### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
AB.sort(key=lambda x:x[0])
AB.append([10**5+1,0])
h=[]
ans=0
for i in range(1,M+1):
  while AB[0][0]<=i:
    heapq.heappush(h,-AB.pop(0)[1])
  if len(h)>0:
    ans+=-heapq.heappop(h)
print(ans)
### BUGGY CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
assert len(A) == N
assert len(B) == M
# K分以内に読む数の最大化

cumA = []
cumB = []
sumA = 0
sumB = 0
for a in A:
  sumA += a
  cumA.append(sumA)
for b in B:
  sumB += b
  cumB.append(sumB)

maximum = 0
for maxA,timeA in enumerate([0]+cumA):
  if timeA > K:
     break
  timeB = K - timeA
  for maxB,timeB in enumerate([0]+cumB):
     if timeA + timeB > K:
        maxB -= 1
        break
  maximum = max(maximum, maxA + maxB)
print(maximum)

### FIXED CODE ###

N , M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a,b=[0],[0]
for i in range(N): a.append(a[i] + A[i])
for i in range(M): b.append(b[i] + B[i])
ans,j=0,M
for i in range(N+1):
  if a[i]>K:
    break
  while b[j] > K - a[i]:
    j -= 1
  ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
    num=a.count(i)
    print(num)

### FIXED CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
c=collections.Counter(a)
for i in range(1,n+1):
    print(c[i])
### BUGGY CODE ###

N = int(input())
# = map(int, input().split())
A = list(map(int, input().split()))
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]
answer = A[0]

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

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


### FIXED CODE ###

N = int(input())
# = map(int, input().split())
A = list(map(int, input().split()))
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]
answer = A[0]

if A.count(0) > 0:
    print(0)
    exit()

for i in range(1, N):
    answer = answer*A[i]
    if answer > 10**18:
        print(-1)
        exit()
else:
    print(answer)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
maximum = -10**9
for i in range(n):
    totalfull = 0; totalcut = 0; count = 0; location = i
    maximumfull = -10**9; maximumcut = -10**9
    for j in range(min(n, k)):
        location = p[location]-1
        totalfull += c[location]
        maximumfull = max(maximumfull, totalfull)
        count += 1
        if location == i: break
    for j in range(k%count):
        location = p[location]-1
        totalcut += c[location]
        maximumcut = max(maximumcut, totalcut)
    maximum = max(maximum, max(maximumfull, max((k//count-1)*totalfull+maximumfull, k//count*totalfull+maximumcut)))
print(maximum)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
maximum = -10**9
for i in range(n):
    totalfull = 0; totalcut = 0; count = 0; location = i
    maximumfull = -10**9; maximumcut = -10**9
    for j in range(min(n, k)):
        location = p[location]-1
        totalfull += c[location]
        maximumfull = max(maximumfull, totalfull)
        count += 1
        if location == i: break
    for j in range(k%count):
        location = p[location]-1
        totalcut += c[location]
        maximumcut = max(maximumcut, totalcut)
    maximum = max(maximum, max(maximumfull, max((k//count-1)*totalfull+maximumfull, k//count*totalfull+maximumcut)))
print(maximum)
### BUGGY CODE ###

import sys
from collections import defaultdict as dd
sys.setrecursionlimit(4100000)

def dfs(node):
  global ts
  visited[node-1] = True
  first_order[node-1] = ts
  ts += 1
  
  for next_node in tree[node]:
    if visited[next_node-1]:
      continue
    dfs(next_node)
  
  last_order[node-1] = ts
  ts += 1

N, Q = map(int, input().split())
tree = dd(list)
visited = [False] * N
first_order = [0] * N
last_order = [0] * N
ts = 0
counter = [0] * N
operation = []
for _ in range(N-1):
  a, b = map(int, input().split())
  tree[a].append(b) 
  tree[b].append(a) 
for _ in range(Q):
  operation.append(tuple(map(int, input().split())))

dfs(1)
for p, x in operation:
  for i in range(N):
    if first_order[p-1] <= first_order[i-1] and last_order[i-1] <= last_order[p-1]:
      counter[i-1] += x
print(*counter)

### FIXED CODE ###

import sys
from collections import defaultdict as dd
sys.setrecursionlimit(4100000)

def dfs(node):
  visited[node-1] = True
  
  for next_node in tree[node]:
    if visited[next_node-1]:
      continue
    counter[next_node-1] += counter[node-1]
    dfs(next_node)

N, Q = map(int, input().split())
tree = dd(list)
visited = [False] * N
counter = [0] * N
operation = []
for _ in range(N-1):
  a, b = map(int, input().split())
  tree[a].append(b) 
  tree[b].append(a) 
for _ in range(Q):
  operation.append(tuple(map(int, input().split())))
  
for p, x in operation:
  counter[p-1] += x
dfs(1)
print(*counter)
### BUGGY CODE ###

def main():
    n,y = map(int, input().split())
    n1000 = y/1000
    n5000 = 0
    n10000 = 0
    a,b,c = -1, -1, -1
    flag = False
    if n <= n1000:
        for bi in range(y//5000+1):
            for ci in range(y//10000+1):
                if n1000-5*bi-10*ci >= 0:
                    if n1000-4*bi-9*ci == n:
                        c = n1000-5*bi-10*ci
                        b = bi
                        a = ci
                        flag = True
                        break
                else:
                    break
            if flag:
                break
    print(int(a),int(b),int(c))
        


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n,y = map(int, input().split())
    aa, ab, ac = -1, -1, -1
    a = y//10000
    b = (y-10000*a)//5000
    c = (y-10000*a-5000*b)//1000
    flag = False
    if n > a+b+c:
        no = n-a-b-c
        for s in range(b+1):
            for t in range(a+1):
                for t1 in range(t+1):
                    for t5 in range(t-t1+1):
                        if s*4 + t1*9 + t5 == no:
                            aa = a-t
                            ab = b-s+t5*2
                            ac = c+s*5+t1*10
                            flag = True
                            break
                    if flag:
                        break
                if flag:
                    break
            if flag:
                break
    elif n == a+b+c:
        aa, ab, ac = a, b, c
    print(aa,ab,ac)


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

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,m=INTM()
    frd=[[] for i in range(n)]
    #print(frd)
    for i in range(m):
        a,b=INTM()
        for k in range(n):
            if ((a in frd[k])or(b in frd[k])):
                if not(a in frd[k]):
                    frd[k].append(a)
                if not(b in frd[k]):
                    frd[k].append(b)
                break
            elif frd[k]==[]:
                frd[k].append(a)
                frd[k].append(b)
                break
            else:
                pass
                
    #print(frd)
    ans=1
    for i in range(n):
        ans=max(ans,len(frd[i]))
    
    print(ans)

                
if __name__=='__main__':
    do()

### FIXED CODE ###

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def do():
    n,m=INTM()
    uf=UnionFind(n)
    for i in range(m):
        a,b=INTM()
        uf.union(a-1,b-1)

    ans=0

    for i in range(n):
        ans=max(ans,uf.size(i))
    
    print(ans)
                
if __name__=='__main__':
    do()
### BUGGY CODE ###

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

cnt = 0
for i in range(1, n):
    a = min(p[:i])
    if a > p[i]:
        cnt += 1
print(cnt + 1)

### FIXED CODE ###

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

cnt = 0
p_min = p[0]
for i in range(n):
    p_min = min(p_min, p[i])
    if p_min == p[i]:
        cnt += 1
print(cnt)
### BUGGY CODE ###

N = int(input())
S = list(input())
for i in range(N):
  if S[i] == 'W':
    S[i] = 1
  else:
    S[i] = 0
ans = N
for i in range(N):
  W = sum(S[0:i])
  E = len(S[i+1:N+1]) - sum(S[i+1:N+1])
  if ans > W+E:
    ans = W+E
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
E = S.count('E')
ans = []
prev = E
pS = 'E'
for i in range(N):
  if S[i] == 'W':
    current = prev
  elif S[i] == 'E':
    current = prev - 1
  if pS == 'W':
    current += 1
  ans.append(current)
  prev = current
  pS = S[i]
print(min(ans))
### BUGGY CODE ###

from itertools import combinations_with_replacement
from collections import Counter
import sys
input = sys.stdin.readline


n = int(input())
a = list(map(int, input().split())) #1-index

#n個のボールから書かれている整数が等しい異なる２つを選ぶ方法
n_l = list(Counter(a).values())
all_p = 0
for i in n_l:
    if i > 1:
        all_p += len((list(combinations_with_replacement(range(1,i), 2))))

#k番目のボールを覗いたn-1個から、k番目のボールと同じ整数を選ぶ方法
for k in range(n):
    print(all_p - (a.count(a[k])-1))


### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
s=Counter(a)
sums=0
for k in s.keys():
    sums+=(s[k]-1)*s[k]//2

for i in a:
    print(sums-s[i]+1)
### BUGGY CODE ###

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

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

AB=[]

A.sort(reverse=True)
A = A[0:K]
B.sort(reverse=True)
B = B[0:K]
for a in A:
    for b in B:
        AB.append(a+b)

AB.sort(reverse=True)

AB = AB[0:K]

ABC=[]
C.sort(reverse=True)
C=C[0:K]
for ab in AB:
    for c in C:
        ABC.append(ab+c)

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])


### FIXED CODE ###

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

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A.sort(reverse=True)
A = A[0:K]
B.sort(reverse=True)
B = B[0:K]
AB = [a+b for a in A for b in B]

AB.sort(reverse=True)

AB = AB[0:K]

C.sort(reverse=True)
C=C[0:K]
ABC = [ab+c for ab in AB for c in C]

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

def main():
    import sys
    from collections import defaultdict
    S=sys.stdin.readline().strip()
    L=[0]*len(S)
    for i in range(len(S)):
        L[-i-1]=int(S[-i-1:])%2019

    dic=defaultdict(int)
    for a in L:
        dic[a]+=1

    
    output=0
    for _,val in dic.items():
        output+=val*(val-1)//2
    
    output+=dic[0]
    print(output)

main()

### FIXED CODE ###

def pow_with_mod(x, n, m):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
            K %= m
        x *= x
        x %= m
        n //= 2

    return (K * x) % m

def main():
    import sys
    S=sys.stdin.readline().strip()
    N=len(S)
    L=[0]*2019
    now=0
    for i in range(N):
        now+=int(S[-i-1])*pow_with_mod(10, i, 2019)
        now%=2019
        L[now]+=1  
    print(L[0]+sum([x*(x-1)//2 for x in L]))
main()