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

x = int(input())
flag = 0
a_s = 0
b_e = int((x+1)/2)
if x == 1:
  print(1, 0)
else:
  for i in range(x+1):
    if i**5 >= x:
      a_s = i
      break
  for b in range(b_e):
    if flag == 1:
      break
    for a in range(a_s-1, x+1):
      if a**5 - b**5 == x:
        print(a, b)
        flag += 1
        break
      elif a**5 + b**5 == x:
        print(a, -1*b)
        flag += 1
        break

### FIXED CODE ###

x = int(input())
def make_divisors(n):
    divisors = [0]
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
    return divisors

flag = 0
a_s = 0
if x == 1:
  print(1, 0)
else:
  l = make_divisors(x)
  for a in range(a_s, x+1):
    if flag == 1:
      break
    for b_a in l:
      if b_a <= a:
        b = a - b_a
        if a**5 - b**5 == x or a**5 + b**5 == x:
          flag += 1
          print(a, b)
          break
      if b_a > a:
        b = b_a - a
        if a**5 + b**5 == x:
          flag += 1
          print(a, -b)
          break
### BUGGY CODE ###

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()
S = nl()
T = nl()

dp = [0] * (M+1)
for i, s in enumerate(S):
    dp2 = dp[:]
    for j, t in enumerate(T):
        dp2[j+1] += dp2[j] - dp[j]
        if s == t:
            dp2[j+1] += dp[j] + 1
    dp = dp2

print((dp[M]+1) % 1000000007)


### FIXED CODE ###

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()
S = nl()
T = nl()

dp = [0] * (M+1)
for i, s in enumerate(S):
    dp2 = dp[:]
    for j, t in enumerate(T):
        dp2[j+1] += dp2[j] - dp[j]
        if s == t:
            dp2[j+1] += dp[j] + 1
    dp = dp2

print((dp[M]+1) % 1000000007)
### BUGGY CODE ###

L,R = map(int,input().split())

ans = 2018
for i in range(L,R):
    for j in range(i+1,R+1):
        tmp = i*j%2019
        if(tmp < ans):
            ans = tmp

print(ans)

### FIXED CODE ###

L,R = map(int,input().split())

if(R-L>=2018):
    print(0)
else:
    ans = 2018
    for i in range(L,R):
        for j in range(i+1,R+1):
            tmp = i*j%2019
            if(tmp < ans):
                ans = tmp
    
    print(ans)
### BUGGY CODE ###

n = int(input())

def calcLucas(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    return calcLucas(n-1) + calcLucas(n-2)

print(calcLucas(n))

### FIXED CODE ###

n = int(input())

l = [0] * 87
l[0] = 2
l[1] = 1
for i in range(2, n + 1):
    l[i] = l[i-1] + l[i-2]
print(l[n])
### BUGGY CODE ###

N,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(N)]
w1=wv[0][0]
wm=max([i[0] for i in wv])

Wlist=[0]+[j*(w1+i) for j in range(1,N+1) for i in range(4)]
dp=[[0]*(4*N+1) for _ in range(N+1)]
#dp[i][j]:N個の物に対して強度(Wlist[j])のバッグ

for i in range(1,N+1):
  w,v=wv[i-1]
  for j in range(4*N+1):
    if w<=Wlist[j]:
      
      ind=0
      d=float("inf")
      for k in range(4*N+1):
        if (Wlist[j]-w)>=Wlist[k] and (Wlist[j]-w)-Wlist[k]<d:
          d=(Wlist[j]-w)-Wlist[k]
          ind=k
      
      dp[i][j]=max(dp[i-1][j],dp[i-1][ind]+v)
    else:
      dp[i][j]=dp[i-1][j]

ind=0
d=float("inf")
for k in range(4*N+1):
  if W>=Wlist[k] and W-Wlist[k]<d:
    d=W-Wlist[k]
    ind=k
print(dp[N][ind])

### FIXED CODE ###

import bisect
N,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(N)]
w1=wv[0][0]

Wlist=[0]+[j*w1+i for j in range(1,N+1) for i in range(3*j+1)]
Wlist=sorted(set(Wlist))
LW=len(Wlist)
dp=[[0]*LW for _ in range(N+1)]
#dp[i][j]:N個の物に対して強度(Wlist[j])のバッグ

for i in range(1,N+1):
  w,v=wv[i-1]
  for j in range(LW):
    if w<=Wlist[j]:      
      ind=bisect.bisect_right(Wlist,Wlist[j]-w)-1
      dp[i][j]=max(dp[i-1][j],dp[i-1][ind]+v)
    else:
      dp[i][j]=dp[i-1][j]

ind=bisect.bisect_right(Wlist,W)-1
print(dp[N][ind])
### BUGGY CODE ###

N = int(input())
S = list(input())

delKeta = N-3
ans = []
for V3 in range(10):
    for i in range(N):
        if(V3==int(S[i])):
            p1=i
            for V2 in range(10):
                for j in range(p1+1,N):
                    if(V2==int(S[j])):
                        p2=j
                
                        for V1 in range(10):
                            for k in range(p2+1,N):
                                if(V1==int(S[k])):
                                    ans.append(S[k]+S[p2]+S[p1])
                                    



print(len(set(ans)))



### FIXED CODE ###

N = int(input())
S = list(map(int,input()))
count = 0

for x100 in range(10):
    if x100 in S[:N-2]:
        ind_100 = S.index(x100)
        
        for x10 in range(10):
            if x10 in S[ind_100+1:N-1]:
                ind_10 = S[ind_100+1:N-1].index(x10) + ind_100 + 1
                
                for x1 in range(10):
                    if x1 in S[ind_10 + 1:]:
                        count += 1
print(count)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

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

    for i in range(K):
        dm = [0]*(N+1)
        for x in range(N):
            dm[max(x - A[x],0)]+=1
            dm[min(x+A[x]+1,N)]-=1
        for j in range(1,N+1):
            dm[j]+=dm[j-1]
        if A[:] == dm[:N]:
            break
        A[:] = dm[:N]
    print(' '.join(map(str,A)))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

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

    for i in range(min(K,50)):
        dm = [0]*N
        for x in range(N):
            dm[max(x - A[x],0)]+=1
            if x+A[x]+1<N:
                dm[x+A[x]+1]+=-1
        for j in range(1,N):
            dm[j]=dm[j-1]+dm[j]
        A[:] = dm[:]
    print(*A)

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


N = int(input())
P = list(map(int, input().split(" ")))

count = 0

for i, value in enumerate(P):

    if i == 0:
        count += 1
        continue

    elif min(P[:i]) >= value:
        count += 1

print(count)

### FIXED CODE ###


N = int(input())
P = list(map(int, input().split(" ")))

count = 0
value = 0

for i, value in enumerate(P):

    if i == 0:
        count += 1
        m = value
        continue

    elif m >= value:
        m = value
        count += 1

print(count)
### BUGGY CODE ###

import math
A,B,N = map(int,input().split())
ans = list()
x = 1
while x <= N:
    ans.append(math.floor(A*x/B)-A*math.floor(x/B))
    if x+1 <= N and ans[x-1] > (math.floor(A*(x+1)/B)-A*math.floor((x+1)/B)):
        break
    else:
      x += 1
print(max(ans))

### FIXED CODE ###

import math
A,B,N = map(int,input().split())
x = min(B-1,N)
print(math.floor(A*x/B)-A*math.floor(x/B))
### BUGGY CODE ###

import numpy as np
import sys

H,W,A,B = map(int,input().split())

if H//2 < B or W//2 < A:
    print("No")
    sys.exit()

ans = np.zeros([H,W],dtype = int)
ans[0:B,0:A]=1
ans[B:,A:]=1
for i in range(H):
    S = list(ans[i,:])
    ans2=''
    for s in S:
         ans2 = ans2 + str(s)
    print(ans2)


### FIXED CODE ###

import sys

H,W,A,B = map(int,input().split())

if H//2 < B or W//2 < A:
    print("No")
    sys.exit()

ans1 = ''
ans2 = ''
for i in range(W):
    if i < A:
        ans1 = ans1 + '1'
        ans2 = ans2 + '0'
    else:
        ans1 = ans1 + '0'
        ans2 = ans2 + '1'

for _ in range(B):print(ans1)
for _ in range(H-B):print(ans2)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def add_link(a, b):
    la = links[a]
    i, j = [(0, 1), (1, 0)][s[b] == 'B']
    if not la[i] and la[j]:
        able[a] = True
    la[i].add(b)

n, m = map(int, input().split())
s = input()
links = [[set(), set()] for _ in range(n)]
able = [False] * n
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    add_link(a, b)
    add_link(b, a)

def erase(v):
  if s[v] == "A":
    l = 0
  else:
    l = 1
  for q in links[v][0]:
    if not able[q]:
      continue
    links[q][l].remove(v)
    if links[q][l] == set():
      able[q] = False
      erase(q)
  for q in links[v][1]:
    if not able[q]:
      continue
    links[q][l].remove(v)
    if links[q][l] == set():
      able[q] = False
      erase(q)

for i in range(n):
  if not able[i]:
    continue
  for k in range(2):
    for j in links[i][k].copy():
      if not able[j]:
        links[i][k].remove(j)
  if (links[i][0] == set() or links[i][1] == set()):
    flag =1
    able[i] = False
    erase(i)
if any(able):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n, m = map(int, input().split())
s = input()
links = [[] for _ in range(2*n)]
visit = [0] * n *2
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    if s[a] == s[b]:
      links[a].append(b+n)
      links[b].append(a+n)
    else:
      links[a+n].append(b)
      links[b+n].append(a)
def dfs(v):
  visit[v] = 1
  for i in links[v]:
    if visit[i] == 1:
      print("Yes")
      exit()
    elif visit[i] == 0:
      dfs(i)
  visit[v] = -1
  
for i in range(n):
  if visit[i] == 0:
    dfs(i)
print("No")
### BUGGY CODE ###

def main():
    class rolling_hash():
        def __init__(self, seq):
            seq_size = len(seq)  # 文字列の長さ
            self.H0s = [0]*(seq_size+1)  # 先頭からi-1文字目までのハッシュ値
            H0s, p = self.H0s, 0
            for i, j in enumerate(seq):
                p = (p+(j+1)*pow(3, i, mod)) % mod
                H0s[i+1] = p

        def calc_hash(self, l, r):  # l文字目からr-1文字目までのハッシュ値
            H0s = self.H0s
            return ((H0s[r]-H0s[l])*pow(3, l*(mod-2), mod)) % mod

    def rolling_hash2(seq):
        p = 0
        for i, j in enumerate(seq):
            p += (j+1)*pow(3, i, mod) % mod
        return p % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a += a
    a1 = [0]*(2*n)
    a2 = [0]*(2*n)
    b1 = [0]*n
    mod = 2**61-1
    memo = [0]*n

    for k in range(32):
        k2 = 2**k
        for i, j in enumerate(a):
            p = (j & k2) >> k
            a1[i] = p
            a2[i] = p ^ 1
        for i, j in enumerate(b):
            b1[i] = (j & k2) >> k
        b_hash = rolling_hash2(b1)
        A1 = rolling_hash(a1)
        A2 = rolling_hash(a2)
        for i, j in enumerate(memo):
            if j is None:
                continue
            elif A1.calc_hash(i, i+n) == b_hash:
                pass
            elif A2.calc_hash(i, i+n) == b_hash:
                memo[i] += k2
            else:
                memo[i] = None

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()

### FIXED CODE ###

def main():
    mod = 2**31-1
    pow3 = [1]*200001
    p = 1
    i3 = pow(3, mod-2, mod)
    for i in range(1, 200001):
        p = p*3 % mod
        pow3[i] = p

    def rolling_hash(seq):
        h = 0
        for i, j in enumerate(seq):
            h += (j+1)*pow3[i]
        h %= mod
        H0s = [0]*n
        for i, j in enumerate(seq):
            H0s[i] = h
            h = (h-j-1+(j+1)*pn)*i3 % mod
        return H0s

    def rolling_hash2(seq):
        p = 0
        p2 = 0
        for i, j in enumerate(seq):
            p += (j+1)*pow3[i]
            p2 += (2-j)*pow3[i]
        return p % mod, p2 % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    m = max(a+b)
    a1 = [0]*n
    b1 = [0]*n
    memo = [0]*n
    cnt = n
    pn = pow3[n]

    for k in range(len(bin(m))-2):
        k2 = 2**k
        for i, j in enumerate(a):
            a1[i] = (j & k2) >> k
        for i, j in enumerate(b):
            b1[i] = (j & k2) >> k
        b_hash, b_hash2 = rolling_hash2(b1)
        A1 = rolling_hash(a1)
        for i, (j, k) in enumerate(zip(memo, A1)):
            if j is None:
                continue
            elif k == b_hash:
                pass
            elif k == b_hash2:
                memo[i] += k2
            else:
                memo[i] = None
                cnt -= 1
        if cnt == 0:
            return

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()
### BUGGY CODE ###

from sys import stdin


def get_result(data):
    _ = data[0][0]
    A = data[1:]
    return len(set(sum(A, [])))


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(str, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)


### FIXED CODE ###

from sys import stdin


def get_result(data):
    N = data[0][0]
    A = data[1:]
    tmp = set()
    for i in range(int(N)):
        tmp.add(A[i][0])
    return len(tmp)


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(str, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)
### BUGGY CODE ###

N, T = map(int,input().split())
A = list(map(int,input().split()))
p = 0
ans = 0
for i in range(1, N):
    t = max(A[i:]) - A[i-1]
    if p == t:
        ans += 1
    elif p < t:
        p = t
        ans = 1
print(ans)


### FIXED CODE ###

import numpy as np
N, T = map(int,input().split())
A = np.array(input().split(), dtype=np.int32)

A_mi = np.minimum.accumulate(A)
pro = A - A_mi

answer = sum(pro == max(pro))
print(answer)
### BUGGY CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n, m, v, p = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    A.sort()

    ret = 0
    for i in range(n):
        if A[i]+m < A[n-p]:
            continue
        pts = m*min(n, i+p)
        for j in range(i+1, n-(p-1)):
            pts += max(0, A[i]+m-A[j])
            if m*v <= pts:
                break

        if m*v <= pts:
            ret += 1

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n, m, v, p = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    A.sort()

    left, right = -1, n

    while left+1 < right:
        i = (left+right)//2

        if A[i]+m < A[n-p]:
            left = i
            continue

        pts = m*min(n, i+p)
        for j in range(i+1, n-(p-1)):
            pts += max(0, A[i]+m-A[j])

        if m*v <= pts:
            right = i
        else:
            left = i

    return str(n-right)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2000000)

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1
N,K,L = map(int,input().split())
roadTree = UnionFind(N)
railTree = UnionFind(N)
for _ in range(K):
    p,q = map(int,input().split())
    roadTree.unite(p,q)
for _ in range(L):
    p,q = map(int,input().split())
    railTree.unite(p,q)

roadGroup = {}
for i in range(1,N+1):
    p = roadTree.find(i)
    if p not in roadGroup:
        roadGroup[p] = [i]
    else:
        roadGroup[p].append(i)

railGroupNum = {}
for i in range(1,N+1):
    p = railTree.find(i)
    railGroupNum[i]=p

ans = [1]*(N)
for p,children in roadGroup.items():
    for i in range(len(children)):
        c1 = children[i]
        for j in range(i+1,len(children)):
            c2 = children[j]
            if railGroupNum[c1] == railGroupNum[c2]:
                ans[c1-1]+=1
                ans[c2-1]+=1
            
print(" ".join([str(a) for a in ans]))

### FIXED CODE ###

"""
道路でつながっているやつが鉄道でもつながっているかどうかを調べるにはどうすればいい？
普通に木ごとのサイズを求めておけばいいのか？

道路ネットワークを根ごとにグルーピングする。その中で、さらに鉄道の根ごとにグルーピングする。
でchooseでペア数を求めれば良い。

"""
import math
import sys
sys.setrecursionlimit(200000)
class UnionFind():
    def __init__(self,n):
        self.parents = [i for i in range(n+1)]

    def find(self,x):
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

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

N,K,L = map(int,input().split())
A = UnionFind(N)
B = UnionFind(N)
for i in range(K):
    p,q = map(int,input().split())
    A.union(p,q)

for i in range(L):
    r,s = map(int,input().split())
    B.union(r,s)


group = {}
for i in range(1,N+1):
    roadRoot = A.find(i)
    if roadRoot not in group:
        group[roadRoot] = {}
    railRoot = B.find(i)
    if railRoot not in group[roadRoot]:
        group[roadRoot][railRoot] = []
    group[roadRoot][railRoot].append(i)

ans = [[]for _ in range(N)]
for i in group.items():
    for j in i[1].values():
        for k in j:
            ans[k-1] = str(len(j))

ans = " ".join(ans)
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
mod=10**9+7
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0 for i in range(m+1)] for i in range(n+1)]
sum=[[0 for i in range(m+1)] for i in range(n+1)]
for i in range(1,n+1):
  for j in range(1,m+1):
    if s[i-1]==t[j-1]:
      dp[i][j]=(sum[i-1][j-1]+1)%mod
    else:dp[i][j]=0
    sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+dp[i][j])%mod
print((sum[-1][-1]+1)%mod)


### FIXED CODE ###

n,m=map(int,input().split())
mod=10**9+7
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0 for i in range(m+1)] for i in range(n+1)]
sum=[[0 for i in range(m+1)] for i in range(n+1)]
for i in range(1,n+1):
  for j in range(1,m+1):
    if s[i-1]==t[j-1]:
      dp[i][j]=(sum[i-1][j-1]+1)%mod
    else:dp[i][j]=0
    sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+dp[i][j])%mod
print((sum[-1][-1]+1)%mod)
### BUGGY CODE ###

n = int(input())
a = []
b = []
for i in range(n):
    c,d = map(int,input().split())
    a.append(c)
    b.append(d)

#下限
all_time = 0
f = n

while(True):
    #上限
    up = min(b)
#    print("up:"+str(up))
#    print(b)
    for i in range(n):
#        print(i)
        if b[i] == up:
            all_time += a[i]
            del b[i]
            del a[i]
#            print(b)
            f -= 1
        if i >= f-1:
            break
            # if i != n-1:
            #     i -= 1
    
    if all_time > up:
        print("No")
#        print(all_time)
        break

#    print("length:"+str(len(b)))
    if len(b) == 0:
        print("Yes")
        break


### FIXED CODE ###

n = int(input())
l = []
for i in range(n):
    c,d = map(int,input().split())
    l.append([c,d])

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

time = 0
ans = "Yes"
for i in range(n):
    limit = l[i][1]
    time += l[i][0]
    if time > limit:
        ans = "No"
        break

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

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
MOD = 10 ** 9 + 7
ans = 0
bit_matrix = [[0] * N for _ in range(61)]
for i in range(len(A)):
    n = 0
    while 2 ** n <= A[i]:
        if A[i] >> n & 1:
            bit_matrix[n][i] = 1
        n += 1
#print(bit_matrix)
#bit_matrix_T = []
'''
for j in range(60):
    tmp = []
    for i in range(N):
        tmp.append(bit_matrix[i][j])
    bit_matrix_T.append(tmp)
'''
#print(bit_matrix_T)
for i in range(len(bit_matrix)):
    tmp = Counter(bit_matrix[i])
    a = list(tmp.values())
    if len(a) == 2:
        ans += (2 ** i) * a[0] * a[1]
        ans %= MOD
print(ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
MOD = 10 ** 9 + 7
ans = 0
bit_matrix = [[0] * N for _ in range(61)]
for i in range(len(A)):
    n = 0
    while 2 ** n <= A[i]:
        if A[i] >> n & 1:
            bit_matrix[n][i] = 1
        n += 1
#print(bit_matrix)
#bit_matrix_T = []
'''
for j in range(60):
    tmp = []
    for i in range(N):
        tmp.append(bit_matrix[i][j])
    bit_matrix_T.append(tmp)
'''
#print(bit_matrix_T)
for i in range(len(bit_matrix)):
    tmp = Counter(bit_matrix[i])
    a = list(tmp.values())
    if len(a) == 2:
        ans += (2 ** i) * a[0] * a[1]
        ans %= MOD
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
string = str(a.index(1) + 1)
for i in range(1, n):
    string += " " + str(a.index(i + 1) + 1)
print(string)


### FIXED CODE ###

import sys
import collections
import bisect


def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = [0] * n
    for i in range(n):
        B[A[i] - 1] = str(i + 1)
    print(" ".join(B))


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

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
nS = int(S)
N = len(S)

nums = []
for i in range(N):
    val = (nS%10)*10**i
    val %= MOD
    nums.append(val)
    nS //= 10
nums.append(0)
nums.reverse()
# print(nums)

d = defaultdict(int)
d[0] += 1
cnt = 0
for i in range(N):
    nums[i+1] += nums[i]
    nums[i+1] %= MOD
    # print(nums[i+1])
    cnt += d[nums[i+1]]
    # print(d[nums[i+1]])
    d[nums[i+1]] += 1
# print(nums)
print(cnt)

### FIXED CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)

d = defaultdict(int)
d[0] += 1
# nums = [0]*(N+1)
m = 0
last = 0
dd = 1
for i in range(N):
    m += int(S[N-i-1])*dd
    m %= MOD
    # val = (int(S[i])*m + nums[i])%MOD
    # cnt += d[val]
    dd = (dd*10)%MOD
    d[m] += 1

cnt = 0
for i, v in d.items():
    cnt += v*(v-1)//2
print(cnt)
### BUGGY CODE ###

L, R = map(int, input().split())

if L - R >= 2019:
    ans = 0
else:
    ans = 2019
    for i in range(L, R):
        x = i % 2019
        for j in range(i + 1, R + 1):
            a = x * j
            ans = min(a % 2019, ans)

print(ans)


### FIXED CODE ###

import sys

L, R = list(map(int, input().split()))

yy = 2019

d = 2019

if R > L+2019:
    R = L+2019

for i in range(L,R):
    im = i % yy

    for j in range(i+1, R+1):
        jm = j % yy

        if im * jm % yy <= d:
            d = im * jm % yy

print(d)
### BUGGY CODE ###

k,s=list(map(int,input().split()))
count=0
for i in range(k+1):
	x=i
	for j in range(k+1):
		y=j
		for l in range(k+1):
			z=l
			if (x+y+z==s):
				count+=1
print (count)

### FIXED CODE ###

k,s=list(map(int,input().split()))
count=0
for i in range(k+1):
	x=i
	for j in range(k+1):
		y=j
		if (s-x-y<=k and x+y<=s):
			count+=1
print (count)