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

def main():
    n, maxW, weight, value = getInputs()

    maxCount = {}
    for w in range(n):
        if str(w) in maxCount:
            maxCount[str(w)] += 1
        else:
            maxCount[str(w)] = 1

    accumulatedValue = [0] * (maxW + 1)
    possible = [False] * (maxW + 1)
    possible[0] = True

    used = []
    for i in range(maxW + 1):
        used.append({})

    for x in range(min(weight), maxW + 1):
        for w in range(n):
            if (x - weight[w] >= 0) and possible[x - weight[w]] \
                and (str(w) not in used[x - weight[w]] or used[x - weight[w]][str(w)] < maxCount[str(w)]):

                if accumulatedValue[x - weight[w]] + value[w] > accumulatedValue[x]:
                    accumulatedValue[x] = accumulatedValue[x - weight[w]] + value[w]
                    used[x] = used[x - weight[w]].copy()
                    if str(w) in used[x]:
                        used[x][str(w)] += 1
                    else:
                        used[x][str(w)] = 1

                    possible[x] = True

    print(max(accumulatedValue))

def getInputs():
    n, maxW = map(lambda x: int(x), input().split())

    weight, value = [], []
    for i in range(n):
        w, v = map(lambda x: int(x), input().split())
        weight.append(w)
        value.append(v)

    return n, maxW, weight, value

main()


### FIXED CODE ###

def main():
    n, maxW, weight, value = getInputs()

    accumulatedValue = [0] * (maxW + 1)

    possible = [False] * (maxW + 1)
    possible[0] = True

    used = []
    for i in range(maxW + 1):
        used.append([0] * n)

    for x in range(min(weight), maxW + 1):
        for w in range(n):
            weightW = weight[w]

            if (x - weightW >= 0) and possible[x - weightW] and used[x - weightW][w] == 0:
                newValue = accumulatedValue[x - weightW] + value[w]

                if newValue > accumulatedValue[x]:
                    accumulatedValue[x] = newValue
                    used[x] = used[x - weightW].copy()
                    used[x][w] = 1
                    possible[x] = True

    print(max(accumulatedValue))

def getInputs():
    n, maxW = map(lambda x: int(x), input().split())

    weight, value = [], []
    for i in range(n):
        w, v = map(lambda x: int(x), input().split())
        weight.append(w)
        value.append(v)

    return n, maxW, weight, value

main()
### BUGGY CODE ###

n, x = map(int,input().split())
xl = list(map(int,input().split()))

xl.append(x)
xl.sort()
sa = []
for i in range(len(xl)-1):
    sa.append(xl[i+1] - xl[i])
    
samin = min(sa)

flag = 0
while flag == 0:
    amari = 0
    for i in sa:
        amari += i % samin
    if amari == 0:
        flag =1
        break
    else:
        for j in range(1,samin+1):
            if samin % j == 0:
                samin = samin // j
                break
print(samin)
        

### FIXED CODE ###

n, x = map(int,input().split())
xl = list(map(int,input().split()))

xl.append(x)
xl.sort()

onesam = 0

if len(xl) == 1:
    print(abs(xl[0] - x))
    exit()

for i in range(len(xl)-1):
    one_sa = xl[i+1] - xl[i]
    if onesam == 0:
        onesam = abs(one_sa)
    else:
        short,big = min(onesam,one_sa),max(onesam,one_sa)
        if big % short == 0:
            onesam = short
            continue
        else:
            while big % short != 0:
                short = short -1
#                 for k in range(2,short+1):
#                     if short % k == 0:
#                         short = short // k
#                         break
            onesam = short
            
print(onesam)
### BUGGY CODE ###

#from pprint import pprint
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#from bisect import bisect_right #二分探索用のモジュール bisect_right(a_list,value)

#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。

# = int(input())

# = map(int,input().split())

# = list(map(int,input().split()))

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

n = int(input())

a = list(map(int,input().split()))

result = 1

for i in range(n):
    result *= a[i]

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


### FIXED CODE ###

#from pprint import pprint
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#from bisect import bisect_right #二分探索用のモジュール bisect_right(a_list,value)

#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。

# = int(input())

# = map(int,input().split())

# = list(map(int,input().split()))

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

n = int(input())

a = list(map(int,input().split()))

result = 1
overflg = 0

if min(a) == 0:
    print(0)
    exit()

for aa in a:
    result *= aa
    if result > 10**18:
        print(-1)
        exit()

print(result)
### BUGGY CODE ###

import sys
import bisect

N, Q = map(int, input().split(' '))
G = [list(map(int, sys.stdin.readline().split(' '))) for _ in range(N)]
T = [int(sys.stdin.readline()) for _ in range(Q)]

G.sort(key = lambda x : -x[2])
T.sort()


class SegTree :
    def __init__(self, n) :
        self.n = n
        self.A = [-2] * (4 * n + 5)

    def update(self, i, l, r, ll, rr, val) :
        if r <= ll or rr <= l :
            return
        if ll <= l and r <= rr :
            self.A[i] = val
            return

        if self.A[i] != -2 :
            self.A[i * 2] = self.A[i * 2 + 1] = self.A[i]
            self.A[i] = -2

        m = (l + r) // 2
        self.update(i * 2, l, m, ll, rr, val)
        self.update(i * 2 + 1, m, r, ll, rr, val)

    def get(self, i, l, r, p) :
        if self.A[i] != -2 or l + 1 == r :
            return self.A[i]
        m = (l+r) // 2
        if p < m :
            return self.get(i * 2, l, m, p)
        else :
            return self.get(i * 2 + 1, m, r, p)

ST = SegTree(Q)
for g in G :
    s = max(0, g[0] - g[2])
    e = g[1] - g[2]
    if e <= 0 :
        continue

    ll = bisect.bisect_left(T, s)
    rr = bisect.bisect_left(T, e)

    if ll == rr :
        continue

    ST.update(1, 0, Q, ll, rr, g[2])

for i in range(Q) :
    ans = ST.get(1, 0, Q, i)
    if ans == -2 :
        print(-1)
    else :
        print(ans)


### FIXED CODE ###

import sys
import bisect
 
N, Q = map(int, input().split(' '))
G = [list(map(int, sys.stdin.readline().split(' '))) for _ in range(N)]
T = [int(sys.stdin.readline()) for _ in range(Q)]

class SegTree :
    def __init__(self, n) :
        self.n = n
        self.A = [10**15] * (2 << (n + 1).bit_length())
 
    def update(self, l, r, val) :
      l += len(self.A) // 2
      r += len(self.A) // 2
      while l < r:
          if l & 1 :
              self.A[l] = min(self.A[l], val)
              l += 1
          if r & 1:
              self.A[r-1] = min(self.A[r-1], val)
              r -= 1
          l //= 2
          r //= 2

    def get(self, i) :
      i += len(self.A) // 2
      ret = self.A[i]
      while i > 0 :
          i //= 2
          ret = min(ret, self.A[i])
      return ret if ret < 10**15 else -1

ST = SegTree(Q)
for g in G :
    s = g[0] - g[2]
    e = g[1] - g[2]
 
    ll = bisect.bisect_left(T, s)
    rr = bisect.bisect_left(T, e)
 
    if ll == rr :
        continue
 
    ST.update(ll, rr, g[2])
 
for i in range(Q) :
    ans = ST.get(i)
    print(ans)
### BUGGY CODE ###

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

ma = max(li)
cnts = []
for i in range(0, ma):
    cnt = li.count(i+1)
    cnts.append(cnt)

for i in cnts:
    print(i)

if ma < n:
    ans = '0\n'*(n-ma)
    print(ans)

### FIXED CODE ###

n = int(input())
list = list(map(int, input().split()))
data = [0] * n

for i in list:
    i -= 1
    data[i] += 1

for j in data:
    print(j)
### BUGGY CODE ###

import re
X = raw_input()
iter = 100000
pat = re.compile('(ST)')

for i in xrange(iter):
    s =	pat.search(X)
    if len(X) == 0:
	break
    if s is	not None:
    	X =	X.replace('ST','')
    else:
	pass
print len(X)

### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    x = S()
    s_cnt = 0
    removed = 0
    for c in x:
        if c == 'S':
            s_cnt += 1
        if c == 'T':
            if s_cnt > 0:
                s_cnt -= 1
                removed += 2
    print(len(x) - removed)
main()
### BUGGY CODE ###

import sys, collections

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    son = [[] for i in range(N)]
    for i in range(M):
        u, v = map(int, input().split())
        son[u-1].append(v-1)
    S, T = map(int, input().split())

    graphB = [set() for i in range(N)]
    q = collections.deque()
    for i in range(N):
        q.append((0, i))
        pathi = set()
        while q:
            cost, now = q.popleft()
            if cost <= 1:
                for s in son[now]: q.append((cost+1, s))
            elif cost == 2: 
                for s in son[now]: pathi |= {s}
        graphB[i] = pathi
    
    visited = [-1] * N
    q.append((0, S-1))
    while q:
        cost, now = q.popleft()
        if visited[now] < 0:
            visited[now] = cost
            for s in graphB[now]:
                if visited[s] < 0: q.append((cost + 1, s))

    print(visited[T-1])
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys, collections

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    son = [[] for i in range(N)] 
    for i in range(M):
        u, v = map(int, input().split())
        son[u-1].append(v-1)
    S, T = map(int, input().split())

    dist = [[-1, -1, -1] for i in range(N)]
    que = collections.deque()
    que.append((0, S-1, 0)) #k回目の移動, 場所, mod
    while que:
        cost, now, mod = que.popleft()
        if dist[now][mod] == -1:
            dist[now][mod] = cost
            if mod == 0:
                for s in son[now]:
                    if dist[s][1] == -1: que.append((cost + 1, s, 1))
            else:
                for s in son[now]:
                    if dist[s][(mod + 1) % 3] == -1: que.append((cost, s, (mod + 1) % 3))

    print(dist[T-1][0])  
    return 0

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

n, k = map(int, input().split())
a = list(map(int, input().split()))

flg = 0
now=1
path=[1]
while flg < k:
    flg = flg+1
    now = a[now-1]
    if now in path:
        flg=k+1
    path.append(now)

if flg == k:
    print(now)
    exit()

x1 = path.index(now)
x2 = len(path)-1
x3 = (k-x1)%(x2-x1)
print(path[x1+x3])



### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))

now=1
flg = 0
path = [1]
pathcheck ={1}
for i in range(k):
    now = a[now-1]
    if now in pathcheck:
        flg = -1
        path.append(now)
        break
    path.append(now)
    pathcheck.add(now)


if flg == 0:
    print(now)
    exit()

x1 = path.index(now)
x2 = len(path)-1
x3 = (k-x1)%(x2-x1)
print(path[x1+x3])
### BUGGY CODE ###

n = int(input())

import fractions
import collections
a = collections.deque(list(map(int, input().split())))
 
lcm = a.popleft()
a.append(lcm)
for i in range(1, n):
    tem = a.popleft()
    lcm = lcm * tem // fractions.gcd(lcm, tem)
    a.append(tem)
 
ans = 0
for i in range(n):
    tem = a.popleft()
    ans += lcm // tem
 
print(ans % (10**9+7))

### FIXED CODE ###

n = int(input())

import fractions
import collections
a = collections.deque(list(map(int, input().split())))
 
lcm = a.popleft()
a.append(lcm)
for i in range(1, n):
    tem = a.popleft()
    lcm = lcm * tem // fractions.gcd(lcm, tem)
    a.append(tem)
 
ans = 0
for i in range(n):
    tem = a.popleft()
    ans += lcm // tem
 
print(ans % (10**9+7))
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(float, input().split()))
for i in range(M):
    A[A.index(max(A))] /= 2
yen = 0
for i in range(N):
    yen += int(A[i])

print(yen)

### FIXED CODE ###

import sys
import math
from collections import deque
import heapq

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, M = NMI()
    A = NLI()
    A = [-a for a in A]
    heapq.heapify(A)
    for i in range(M):
        a_max = -heapq.heappop(A)
        a_max = a_max // 2
        heapq.heappush(A, -a_max)
    print(-sum(A))



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

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def main():
    n = int(input())
    al = list(map(int, input().split())) 
    lcm_dic = {}
    al_facs = []
    for a in al:
        fac = factorization(a)
        a_fac_dic = {}
        for f in fac:
            lcm_dic.setdefault(f[0],0)
            lcm_dic[f[0]] = max(f[1], lcm_dic[f[0]])
            a_fac_dic[f[0]] = f[1]
        al_facs.append(a_fac_dic)

    # lcm = 1
    # for prim, cnt in lcm_dic.items():
    #     lcm *= (prim**cnt)
    # # print(lcm)

    # ans = 0
    # for a in al:
    #     ans += lcm//a
    #     ans%=(10**9+7)
    # print(ans)

    ans = 0
    for al_f in al_facs:
        curr_val = 1
        for prime, cnt in lcm_dic.items():
            if prime in al_f:
                curr_val *= (prime**(cnt-al_f[prime]))
            else:
                curr_val *= (prime**cnt)
        ans += curr_val
        ans %= (10**9+7)
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import deque, Counter, defaultdict

input = sys.stdin.readline
MOD = (10**9+7)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr


def pow_k1(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x


def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        x%=MOD
    return K * x


def main():
    n = int(input())
    al = list(map(int, input().split())) 
    lcm_dic = defaultdict(int)
    # lcm_dic = {}
    # al_facs = []
    for a in al:
        fac = factorization(a)
        # a_fac_dic = {}
        for f in fac:
            # lcm_dic.setdefault(f[0],0)
            lcm_dic[f[0]] = max(f[1], lcm_dic[f[0]])
            # a_fac_dic[f[0]] = f[1]
        # al_facs.append(a_fac_dic)


    lcm = 1
    for prime, cnt in lcm_dic.items():
        lcm *= pow_k1(prime,cnt)

    
    ans = sum( [ lcm//a for a in al] ) % MOD
    # ans = 0
    # for a in al:
    #     ans += lcm//a
    #     ans%=MOD


    # ans = 0
    # for al_f in al_facs:
    #     curr_val = 1
    #     for prime, cnt in lcm_dic.items():
    #         if prime in al_f:
    #             curr_val *= pow_k(prime,(cnt-al_f[prime]))
    #             curr_val%=MOD
    #         else:
    #             curr_val *= pow_k(prime,cnt)
    #             curr_val%=MOD
    #     ans += curr_val
    #     ans %= MOD
    print(ans)


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

from fractions import gcd
from functools import reduce

MOD=10**9+7

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

N=int(input())
A=list(map(int, input().split()))
lcm=reduce(lcm_base, A, 1)
ans=0
for i in range(N):
  ans+=lcm//A[i]
print(ans%MOD)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

MOD=10**9+7

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

N=int(input())
A=list(map(int, input().split()))
ans=1
lcm=A[0]
for i in range(1, N):
  prelcm=lcm
  lcm=lcm_base(prelcm, A[i])
  ans=ans*(lcm//prelcm)+lcm//A[i]
print(ans%MOD)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    S = S[::-1]
    N = len(S)
    dp = [[0 for j in range(13)] for i in range(N)]

    for i in range(N):
        c = S[i]
        if i == 0:
            if c == '?':
                for j in range(10):
                    dp[i][j] = 1
            else:
                dp[i][int(c)] = 1
        else:
            for k in range(13):
                if c == '?':
                    for j in range(10):
                        amari = (j * (10 ** i)) % 13
                        dp[i][k] = (dp[i][k] + dp[i-1][(k-amari)%13]) % MOD
                else:
                    amari = (int(c) * (10 ** i)) % 13
                    dp[i][k] += (dp[i][k] + dp[i - 1][(k-amari) % 13]) % MOD

    dprint(dp)
    print(dp[N-1][5])

solve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    S = S[::-1]
    N = len(S)
    dp = [0 for j in range(13)]
    dp2 = [0 for j in range(13)]

    for i, c in enumerate(S):
        if i == 0:
            if c == '?':
                for j in range(10):
                    dp[j] = 1
            else:
                dp[int(c)] = 1
        else:
            if c == '?':
                for j in range(10):
                    amari = (j * pow(10, i, 13)) % 13
                    for k in range(13):
                        dp2[k] = (dp2[k] + dp[(k-amari)%13]) % MOD
            else:
                for k in range(13):
                    amari = (int(c) * pow(10, i, 13)) % 13
                    dp2[k] = (dp2[k] + dp[(k-amari) % 13]) % MOD

            dp = dp2
            dp2 = [0 for j in range(13)]

    dprint(dp)
    print(dp[5])



solve()
### BUGGY CODE ###

a = list(input().split(" "))
x = int(a[0])
if x < 0:
    x *= -1
k = int(a[1])
d = int(a[2])

for i in range(k):
    x -= d
    if x <= 0:
        if (k - i) % 2 == 1:
            x *= -1
            break
        else:
            x += d
            break

print(x)

### FIXED CODE ###

a = list(input().split(" "))
x = int(a[0])
if x < 0:
    x *= -1
k = int(a[1])
d = int(a[2])
c = x // d

if c >= k:
    x -= d * k
else:
    x -= d * c
    if (k - c) % 2 == 1:
        x = (x - d) * -1

print(x)
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    a = list(map(int, input().split()))

    if 0 in a:
        print(0)
    else:
        cur = 1
        for x in a:
            cur *= x
        if cur > 10 ** 18:
            print(-1)
        else:
            print(cur)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    a = list(map(int, readline().split()))
    a.sort()
    
    cur = 1
    for x in a:
        cur *= x
        if cur > 10 ** 18:
            print(-1)
            sys.exit()

    print(cur)


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

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

ship = []
count = 0

for i in range(m):
    if count != 0:
        break
    if ab[i][1] == n:
        for j in range(m):
            if i == j:
                continue
            elif ab[i][0] == ab[j][1] and ab[j][0] == 1:
                print('POSSIBLE')
                count += 1
                break
            else:
                continue

if count == 0:
    print('IMPOSSIBLE')


### FIXED CODE ###

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

ship_list1 = []
ship_list2 = []
count = 0
loop = False

for i in range(m):
    if ab[i][0] == 1:
        ship_list1.append(ab[i][1])
    if ab[i][1] == n:
        ship_list2.append(ab[i][0])

if len(set(ship_list1) & set(ship_list2)) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

from collections import deque
from math import ceil
H, W = [int(i) for i in input().split()]
s = [input() for _ in range(H)]

dq = deque()
D = [[999999999999]*W for _ in range(H)]
if s[0][0] == '.':
    D[0][0] = 0
else:
    D[0][0] = 1
dq.append((1, 0, s[0][0], D[0][0]))
dq.append((0, 1, s[0][0], D[0][0]))

while len(dq):
    h, w, m, d = dq.popleft()
    if s[h][w] != m:
        d += 1
    D[h][w] = min(D[h][w], d)

    for nh, nw in ((h+1, w), (h, w+1)):
        if nh < H and nw < W:
            dq.append((nh, nw, s[h][w], d))
print(ceil(D[-1][-1]/2))


### FIXED CODE ###

from collections import deque
from math import ceil
H, W = [int(i) for i in input().split()]
s = [input() for _ in range(H)]

dq = deque()
D = [[999999999999]*W for _ in range(H)]
if s[0][0] == '.':
    D[0][0] = 0
else:
    D[0][0] = 1
dq.append((0, 0, s[0][0]))

while len(dq):
    h, w, m = dq.popleft()
    d = D[h][w]

    for nh, nw in ((h+1, w), (h, w+1)):
        if nh < H and nw < W:
            if D[nh][nw] == 999999999999:
                dq.append((nh, nw, s[nh][nw]))
            if s[nh][nw] != m:
                D[nh][nw] = min(D[nh][nw], d+1)
            else:
                D[nh][nw] = min(D[nh][nw], d)

print(ceil(D[-1][-1]/2))
### BUGGY CODE ###

def main():
    import sys
    from collections import Counter

    input = sys.stdin.readline

    s = str(input().rstrip())
    num = ""
    li = []
    f = 0
    mi = 0

    for i in range(1, len(s) + 1):
        num = s[-i] + num
        li.append(int(num) % 2019)
        if num[0] == "0":
            f += 1
        else:
            if f > 0:
                mi += ((f + 1) * f) // 2
                f = 0

    co = Counter(li)
    val = co.values()
    ans_1 = 0

    for i in val:
        if i > 1:
            ans_1 += (i * (i - 1)) // 2
        else:
            continue
    ans2 = 0
    if 0 in co:
        zero = co[0]
        ans2 = zero
    print(ans_1 + ans2 - mi)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import sys
    from collections import defaultdict
    dic = defaultdict(int)

    input = sys.stdin.readline

    s = str(input().rstrip())
    m = 0
    before_m = 0.1

    for i in range(1, len(s) + 1):
        before_m = int(before_m*10)%2019
        m_ad = (int(s[-i]) * before_m) % 2019
        m = (m_ad + m) % 2019
        dic[m] += 1

    ans1 = 0

    for x in dic.values():
        if x > 1:
            ans1 += x * (x - 1) // 2
    ans2 = dic[0]

    print(ans1 + ans2)

if __name__ == "__main__":
    main()