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

S = input()
S = S[::-1]
ans = [[0] * 13 for _ in range(len(S))]
MOD = 10 ** 9 + 7
if S[0] == "?":
    for i in range(10):
        ans[0][i] = 1
else:
    ans[0][int(S[0])] = 1

for i, s in enumerate(S):
    if i == 0:
        continue
    if s == "?":
        for n in range(10):
            for j in range(13):
                if ans[i - 1][j] == 0:
                    continue
                ans[i][(j + n * 10 ** i) % 13] += ans[i - 1][j]
                ans[i][(j + n * 10 ** i) % 13] %= MOD
    else:
        for j in range(13):
            ans[i][(j + int(s) * 10 ** i) % 13] = ans[i - 1][j]

print(ans[-1][5])


### FIXED CODE ###

S = input()
ans = [[0] * 13 for _ in range(len(S))]
MOD = 10 ** 9 + 7
if S[0] == "?":
    for i in range(10):
        ans[0][i] = 1
else:
    ans[0][int(S[0])] = 1

for i, s in enumerate(S):
    if i == 0:
        continue
    if s == "?":
        for n in range(10):
            for j in range(13):
                ans[i][(j * 10 + n) % 13] += ans[i - 1][j]
                ans[i][(j * 10 + n) % 13] %= MOD
    else:
        for j in range(13):
            ans[i][(j * 10 + int(s)) % 13] = ans[i - 1][j]

print(ans[-1][5])
### BUGGY CODE ###

from functools import reduce
S = list(map(int,input().rstrip()))
l=len(S)
result=0
for i in range(0,int(l-3)):
    for j in range(i+4,int(l+1)):
        n = reduce( lambda a,b:10*a+b, S[i:j])
        if n %2019==0:
            result+=1
print(result)

### FIXED CODE ###

# coding: utf-8
# Your code here!
def main():
    from functools import reduce
    import collections
     
    S = list(map(int,input().rstrip()))
    N=len(S)
    mod_list = [0]
    for i in range(1,N+1):
        new1 =pow(10,i-1,2019)
        new = (new1*S[-i]+mod_list[-1])%2019
        #print(new)
        mod_list.append(new)
        
    count = collections.Counter(mod_list)
    ans =0
    for j in range(2019):
        n = count[j]
        ans+= n*(n-1)/2
    print(int(ans))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import time
import copy

d,g = map(int,input().split())
P = []
C = []
for i in range(d):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

# start = time.time()

m = 10**9

def flag(point,P,now):
    if point+100*(now+1)*P >= g:
        return 1
    else:
        return 0

def score(point = 0, n = 0, now=0, done=[]):
    global m
    if point >= g:
        if m > n: m = n
    elif flag(point,P[now],now):
            for i in range(1,P[now]+1):
                point += 100*(now+1)
                n += 1
                if point >= g:
                    if m > n:
                        m = n
                        break
    else:
        donecp = copy.deepcopy(done)
        donecp.append(now)
        for i in range(d):
            if not i in donecp:
                score(point+P[now]*100*(now+1) + C[now], n + P[now], i, donecp)

for i in range(d):
    done = []
    score(0,0,i,done)

# elapsed_time = time.time() - start

print(m)

### FIXED CODE ###

import math
 
d,g = [int(i) for i in input().split()]
P = []
C = []
for i in range(d):
    p,c = [int(i) for i in input().split()]
    P.append(p)
    C.append(c)

# cnt = 0
# def count():
#     global cnt
#     cnt+=1
#     print(cnt)

def flag(point,P,now):
    if point+100*(now+1)*(P-1) >= g: return 1
    elif point+100*(now+1)*P + C[now] >= g: return 2
    else: return 0

m = 10**9
def score(point = 0, n = 0, now=-1, remain = list(range(d))):
    global m
    if m <= n: return
    elif now == -1:
        for i in remain:
            score(point, n, i, remain)
    elif point >= g: m = n
    elif flag(point,P[now],now) == 1:
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: m = n
    elif flag(point,P[now],now) == 2:
        n += P[now]
        if m > n: m = n
    else:
        if m <= n+P[now]: return
        else:
            remain = remain[:]
            remain.remove(now)
            nxtp = point + P[now]*100*(now+1) + C[now]
            for i in remain:
                score(nxtp, n + P[now], i, remain)

score()
print(m)
### BUGGY CODE ###

n,d = map(int,input().split())
num = [[0]*d for i in range(d)]
a = 0
for i in range(n):
  x,y = map(int,input().split())
  x %=d
  y%=d
  num[x][y] += 1
  a = max(a,num[x][y])
x=1
while x*x<a:
  x += 1
r = (x-1)*d
a = x-1
dai = d-1
syo = 0
def cheak(kon):
  for i in range(d):
    for j in range(d):
      flag = 1
      for k in range(d):
        i2 = (i+k)%d
        for l in range(d):
          j2 = (j+l)%d
          if k<= kon and l<= kon:
            if num[i2][j2] > (a+1)**2:
              flag = 0
          elif kon < k and kon < l:
            if num[i2][j2] > a**2:
              flag = 0
          else:
            if num[i2][j2] > a*(a+1):
              flag = 0
      if flag:
        return 1
  return 0
kon = (dai+syo)//2
while True:
  if dai-syo <= 1:
    if cheak(syo) == 1:
       dai = syo
    break
  kon = (dai+syo)//2
  c = cheak(kon)
  if c == 1:
    dai = kon
  else:
    syo = kon
print(dai+r)

### FIXED CODE ###

n,d = map(int,input().split())
num = [[0]*d for i in range(d)]
a = 0
for i in range(n):
  x,y = map(int,input().split())
  x %=d
  y%=d
  num[x][y] += 1
  a = max(a,num[x][y])
x=1
while x*x<a:
  x += 1
r = (x-1)*d
a = x-1
dai = d-1
syo = 0
anum = [[[0]*d for i in range(d)]for i in range(3)]
rui = [[[0]*(2*d+1) for i in range(2*d+1)]for i in range(3)]
for i in range(d):
  for j in range(d):
    z = num[i][j]
    if z > (a+1)**2:
      anum[0][i][j]=1
      anum[1][i][j]=1
      anum[2][i][j]=1
    elif z> a*(a+1):
      anum[1][i][j]=1
      anum[2][i][j]=1
    elif z > a*a:
      anum[1][i][j]=1
for x in range(3):
  for i in range(1,2*d+1):
    for j in range(1,2*d+1):
      rui[x][i][j]+=rui[x][i-1][j]+rui[x][i][j-1]-rui[x][i-1][j-1]+anum[x][(i-1)%d][(j-1)%d]
def cheak(kon):
  for i in range(1,d+1):
    for j in range(1,d+1):
      if rui[0][i+kon][j+kon] - rui[0][i - 1][j+kon] - rui[0][i+kon][j - 1] + rui[0][i - 1][j - 1]:
        continue
      if rui[1][i+d-1][j+d-1] - rui[1][i+kon+1 - 1][j+d-1] - rui[1][i+d-1][j+kon+1 - 1] + rui[1][i+kon+1 - 1][j+kon+1 - 1]:
        continue
      if rui[2][i+d-1][j+kon] - rui[2][i+kon+1 - 1][j+kon] - rui[2][i+d-1][j - 1] + rui[2][i+kon+1 - 1][j - 1]:
        continue
      if rui[2][i+kon][j+d-1] - rui[2][i - 1][j+d-1] - rui[2][i+kon][j+kon+1 - 1] + rui[2][i - 1][j+kon+1 - 1]:
        continue
      return 1
  return 0 
kon = (dai+syo)//2
while True:
  if dai-syo <= 1:
    if cheak(syo) == 1:
       dai = syo
    break
  kon = (dai+syo)//2
  c = cheak(kon)
  if c == 1:
    dai = kon
  else:
    syo = kon
print(dai+r)
### BUGGY CODE ###


# 二部探索で決めていく。dpですでに見られたかどうかは把握
"""
工事 finish  1 eve削除
工事 start   2 eve追加
di start     3
この時間を混ぜてソート。上から順番に捌く
（区間がxi,xjで重なっていたらsetに入れられないのか。）

同じ時刻だった場合
工事finish -> 工事start -> di通過
の順番
"""
import sys
from operator import itemgetter
input = sys.stdin.readline
n,q  = map(int, input().split())
events = []
E = 10**10
for i in range(n):
    s,t,x = map(int, input().split())
    # st
    events.append((s-x,1,x))
    # gl
    events.append((t-x,0,x))
ds = [(int(input()),2,i) for i in range(q)]
events.extend(ds)
ans = [-1] * q
events.sort()
works = set()
upd = True
mn = 10**10
for t, e, x in events:
    if e == 1:
        works.add(x)
        if mn > x:
            mn = x
            upd = False
    elif e == 0:
        works.remove(x)
        if x == mn:
            upd = True
    else:
        if len(works) == 0:
            ans[x] = -1
        else:
            if upd:
                mn = min(works)
                upd = False
            ans[x] = mn
print(*ans)

    

### FIXED CODE ###


# 二部探索で決めていく。dpですでに見られたかどうかは把握
"""
工事 finish  1 eve削除
工事 start   2 eve追加
di start     3
この時間を混ぜてソート。上から順番に捌く
（区間がxi,xjで重なっていたらsetに入れられないのか。）

同じ時刻だった場合
工事finish -> 工事start -> di通過
の順番
"""
import sys
from operator import itemgetter
input = sys.stdin.readline
n,q  = map(int, input().split())
events = []
E = 10**10
for i in range(n):
    s,t,x = map(int, input().split())
    # st
    events.append((s-x,1,x))
    # gl
    events.append((t-x,0,x))
ds = [(int(input()),2,i) for i in range(q)]
events.extend(ds)
ans = [-1] * q
events.sort()
works = set()
upd = True
mn = 10**10
for t, e, x in events:
    if e == 1:
        works.add(x)
        if mn > x:
            mn = x
            upd = False
    elif e == 0:
        works.remove(x)
        if x == mn:
            upd = True
    else:
        if len(works) == 0:
            ans[x] = -1
        else:
            if upd:
                mn = min(works)
                upd = False
            ans[x] = mn
print(*ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
K, S = map(int, input().split())
ans = 0

for X in range(K + 1):
    for Y in range(X, K + 1):
        for Z in range(Y, K + 1):
            if X + Y + Z == S:
                if len(set([X, Y, Z])) == 1:
                    ans += 1
                elif len(set([X, Y, Z])) == 2:
                    ans += 3
                else:
                    ans += 6
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
K, S = map(int, input().split())
ans = 0

for X in range(K + 1):
    for Y in range(X, K + 1):
        Z = S - Y - X
        if Z >= Y and Z <= K:
                
            if len(set([X, Y, Z])) == 1:
                ans += 1
            elif len(set([X, Y, Z])) == 2:
                ans += 3
            else:
                ans += 6
print(ans)
### BUGGY CODE ###

from collections import deque

N = int(input())
abc = [list(map(int, input().split())) for _ in range(N-1)]

Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

g = [[] for _ in range(N+1)]
dist = [[-1]*(N+1) for _ in range(N+1)]
for a, b, c in abc:
    g[a].append(b)
    g[b].append(a)
    dist[a][b] = c
    dist[b][a] = c

f_inf = float('inf')
cost = [f_inf] * (N+1)
cost[K] = 0
temp = deque([K])

while temp:
    p = temp.popleft()
    for q in g[p]:
        c = cost[p] + dist[p][q]
        if cost[q] >= c:
            cost[q] = c
            temp.append(q)
            
for x, y in xy:
    print(cost[x] + cost[y])


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())

g = [[] for _ in range(N+1)]

for i in range(N-1):
    a, b, c = map(int, input().split())
    g[a].append([b, c])
    g[b].append([a, c])
    
Q, K = map(int, input().split())

cost = [-1] * (N+1)
cost[K] = 0
temp = [K]
while temp:
    p = temp.pop()
    for q in g[p]:
        if cost[q[0]] == -1:
            cost[q[0]] = cost[p] + q[1]
            temp.append(q[0])

for i in range(Q):
    x, y = map(int, input().split())
    print(cost[x] + cost[y])
### BUGGY CODE ###

import sys
h,w=map(int,sys.stdin.readline().split())
from itertools import *
g=[input() for _ in range(h)]
cw=[[] for _ in range(h)]
for i in range(h):
  gw=[(s,len(list(c))) for s,c in groupby(g[i])]
  for s,c in gw:
    if s=='.': cw[i]+=[c]*c
    else: cw[i]+=[0]*c
gt=list(zip(*g))
ch=[[] for _ in range(w)]
for i in range(w):
  gh=[(s,len(list(c))) for s,c in groupby(gt[i])]
  for s,c in gh:
    if s=='.': ch[i]+=[c]*c
    else: ch[i]+=[0]*c
ch=list(zip(*ch))
print(max(cw[i][j]+ch[i][j]-1 for i in range(h) for j in range(w)))

### FIXED CODE ###

h,w=map(int,input().split())
f=lambda:[[0]*w for _ in range(h)]
g=[input() for _ in range(h)]
l,r=f(),f()
for i in range(h):
  lc=rc=0
  for j in range(w):
    if g[i][j]=='.': lc+=1; l[i][j]=lc
    else: lc=0
    if g[i][-1-j]=='.': rc+=1; r[i][-1-j]=rc
    else: rc=0
d,u=f(),f()
for i in range(w):
  dc=uc=0
  for j in range(h):
    if g[j][i]=='.': dc+=1; d[j][i]=dc
    else: dc=0
    if g[-1-j][i]=='.': uc+=1; u[-1-j][i]=uc
    else: uc=0
print(max(l[i][j]+r[i][j]+d[i][j]+u[i][j]-3 for i in range(h) for j in range(w)))
### BUGGY CODE ###

import numpy as np
from collections import deque

S = input()
Q = int(input())
reverse_cnt = 0
index = np.array([0 for _ in range(Q)])
s = deque([])

for i in range(Q):
    query = input().split()
    if query[0] == "1":
        reverse_cnt += 1
        index = index * -1
    else:
        s.append(query[2])
        if query[1] == "1":
            index[i] = -1
        else:
            index[i] = 1

if reverse_cnt % 2 != 0:
    S = S[::-1]
    
for i in index:
    if i == 1:
        S += s.popleft()
    elif i == -1:
        S = s.popleft() + S

print(S)

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
reverse_cnt = 0
s = deque([i for i in S])

for i in range(Q):
    query = input().split()
    if query[0] == "1":
        reverse_cnt += 1
    else:
        if query[1] == "1":
            if reverse_cnt % 2 == 0:
                s.appendleft(query[2])
            else:
                s.append(query[2])
        else:
            if reverse_cnt % 2 == 0:
                s.append(query[2])
            else:
                s.appendleft(query[2])

if reverse_cnt % 2 == 0:
    while s:
        print(s.popleft(), end="")
else:
     while s:
        print(s.pop(), end="")
### BUGGY CODE ###

import collections
n = int(input())
a = list(map(int, input().split()))
# a = 
# b = 10
# gcd_list = []
# for i in range(n-1):
#     gcd_list.appned(gcd(a[i],a[i+1]))
# divisors_ll = []
# def gcd(n, a):

#     a_list = []
#     b_list = []
#     for i in range(1,a+1):
#         a_list.append(int(a//i))
#     for i in range(1,b+1):
#         b_list.append(int(b//i))
#     set_list = list(set(a_list) & set(b_list))
#     return max(set_list))
gcd_l = []
divisors_ll = []
for i in range(len(a)):
    divisors_ll.append([int(a[i]//j) for j in range(1,a[i]+1) if a[i]%j == 0])
for i in range(len(a)):
    divisors_ll_copy = divisors_ll.copy()
    divisors_ll_copy.pop(i)
    divisors_ll_copy
    tmp_l = [flatten for inner in divisors_ll_copy for flatten in inner]
    c = collections.Counter(tmp_l)
    tmp = []
    for v, count in c.most_common():
        if count == (len(a)-1):
            tmp.append(v)
    gcd_l.append(max(tmp))
print(max(gcd_l))



### FIXED CODE ###

# import math
n = int(input())
s = list(map(int,input().split()))

def gcd(a,b):
    if (a==0) or (b==0):
        return max(a,b) 
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

lm = [0] *(n+1)
rm = [0] *(n+1)
for i in range(1,n):
    lm[i+1] = gcd(lm[i],s[i-1])
for i in range(n-1,0,-1):
    rm[i] = gcd(rm[i+1],s[i])

ans = float('-inf')
for i in range(1,n+1):
    ans = max(ans,gcd(lm[i],rm[i]))
print(ans)
### BUGGY CODE ###

N = int(input())
S = [int(x) for x in list(input())]
total = []
for x in range(N-2):
  for y in range(x+1,N-1):
    for z in range(y+1,N):
      total.append(S[x]*100+S[y]*10+S[z])
print(len(set(total)))


### FIXED CODE ###

N = int(input())
S = [int(x) for x in list(input())]
total = 0
for a in range(1000):
  tmp = [a//100,a//10%10,a%10]
  i = 0
  for x in range(N):
    if tmp[i] == S[x]:
      i+=1
    if i==3:
      total+=1
      break
print(total)
### BUGGY CODE ###

from sys import stdin, stdout
import math,sys,heapq
from itertools import permutations, combinations
from collections import defaultdict,deque,OrderedDict
from os import path
import bisect as bi
def yes():print('YES')
def no():print('NO')
if (path.exists('input.txt')): 
    #------------------Sublime--------------------------------------#
    sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
    def I():return (int(input()))
    def In():return(map(int,input().split()))
else:
    #------------------PYPY FAst I/o--------------------------------#
    def I():return (int(stdin.readline()))
    def In():return(map(int,stdin.readline().split()))

def dict(a):
    d={}
    for x in a:
        if d.get(x,-1)!=-1:
            d[x]+=1
        else:
            d[x]=1
    return d

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bi.bisect_right(a, x)
    if i != len(a):
        return i
    else:            
        return -1

def main():
    try:
        n,k=In()
        l=list(In())   
        ans=[]
        t=1
        last=1
        for x in range(n):
            if x<k:
                last*=l[x]
            else:
                temp=last//l[x-k]
                temp*=l[x]
                if temp>last:
                    stdout.write('Yes'+'\n')
                else:
                    stdout.write('No'+'\n')
                last=temp
        
            

    except:
        pass
        
M = 998244353
P = 1000000007
 
if __name__ == '__main__':
    #for _ in range(I()):main()
    for _ in range(1):main()




### FIXED CODE ###

from sys import stdin, stdout
import math,sys,heapq
from itertools import permutations, combinations
from collections import defaultdict,deque,OrderedDict
from os import path
import bisect as bi
def yes():print('YES')
def no():print('NO')
if (path.exists('input.txt')): 
    #------------------Sublime--------------------------------------#
    sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
    def I():return (int(input()))
    def In():return(map(int,input().split()))
else:
    #------------------PYPY FAst I/o--------------------------------#
    def I():return (int(stdin.readline()))
    def In():return(map(int,stdin.readline().split()))

def dict(a):
    d={}
    for x in a:
        if d.get(x,-1)!=-1:
            d[x]+=1
        else:
            d[x]=1
    return d

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bi.bisect_right(a, x)
    if i != len(a):
        return i
    else:            
        return -1

def main():
    try:
        n,k=In()
        l=list(In())   
        ans=[]
        t=1
        last=1
        for x in range(k,n):
            if l[x-k]>=l[x]:
                print('No')
            else:
                print('Yes')


    except:
        pass
        
M = 998244353
P = 1000000007
 
if __name__ == '__main__':
    #for _ in range(I()):main()
    for _ in range(1):main()
### BUGGY CODE ###

def main():
    from collections import deque
    import sys

    n,m =map(int,input().split())
    abl=[[] for i in range(n)]
    for i in range(m):
        a,b = map(int,input().split())
        abl[a-1].append(b)
        abl[b-1].append(a)

    an=[0]*(n-1)
    tg = deque([1])
    wwk =deque([])
    con =0

    while con<=m*2:
        while len(tg)!=0:
            itg = tg.pop()
            wk =deque(abl[itg-1])
            for j in range(len(wk)):
                iwk=wk.pop()
                con += 1
                if an[iwk-2]==0 and iwk!=1:
                    an[iwk-2]=itg
                    wwk.append(iwk)
                if all(an):
                    print('Yes')
                    for j in an:
                        print(j)
                    sys.exit()
        tg=deque(wwk)
        wwk =deque([])

    print('No')


main()

### FIXED CODE ###

def main():
    from collections import deque
 
    n,m =map(int,input().split())
    abl=[[] for i in range(n+1)]
    for i in range(m):
        a,b = map(int,input().split())
        abl[a].append(b)
        abl[b].append(a)
 
    an=[0]*(n+1)
    an[0]=1
    tg = deque([1])
    while len(tg):
        itg = tg.popleft()
        for j in abl[itg]:
            if an[j]==0:
                an[j]=itg
                tg.append(j)

    if all(an):
        print('Yes')
        for j in an[2:]:
            print(j)
    else:
        print('No')
 
main()
### BUGGY CODE ###

import sys
n,m=map(int,input().split())
arr=[1,2]
arr=arr+[0]*(n-2)
danger=tuple(map(int,sys.stdin))
if 1 in danger:
  arr[0]=0
  arr[1]=1
for i in range(n):
  if i+1 in danger:
    arr[i]=0
  elif i==0 or i==1:
    continue 
  else:
    arr[i]=(arr[i-1]+arr[i-2])%(10**9+7)
print(arr[n-1]%(10**9+7))


### FIXED CODE ###

import sys
n,m = map(int,input().split())
a = list(map(int,sys.stdin))
a.append(0)
prev=0
cur=1
m=0
for i in range(1,n+1):
  if a[m]==i:
    prev,cur = cur,0
    m += 1
  else:
    prev,cur = cur,(cur+prev)%1000000007
print(cur)
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
    ans *= i
print(ans%(10**9+7))

### FIXED CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
    ans *= i
    ans = ans%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

def main():
    from collections import deque

    H, W = map(int, input().split())
    g = [str(input()) for _ in range(H)]
    ans = 0
    dh = [1, 0, 0, -1]
    dw = [0, -1, 1, 0]
    for h in range(H):
        for w in range(W):
            if g[h][w] == '.':
                d = 0
                done = [[False] * W for _ in range(H)]
                done[h][w] = True
                q = deque([[h, w]])
                while q:
                    h, w = q.popleft()
                    d += 1
                    for i in range(4):
                        nh = h + dh[i]
                        nw = w + dw[i]
                        if 0 <= nh < H and 0 <= nw < W and done[nh][nw] == False:
                            if g[nh][nw] == '.':
                                done[nh][nw] = True
                                q.append([nh, nw])
                            else:
                                q.clear()
                                break
                ans = max(ans, d)
    print(ans)
main()

### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    g = []
    q = []
    cnt = 0
    for h in range(H):
        A = str(input())
        row = []
        for w in range(W):
            row.append(A[w])
            if A[w] == '#':
                cnt += 1
                q.append([h, w])
        g.append(row)
    ans = 0
    dh = [1, 0, 0, -1]
    dw = [0, -1, 1, 0]
    while cnt < H * W:
        ans += 1
        nextq = []
        while q:
            h, w = q.pop()
            for i in range(4):
                nh = h + dh[i]
                nw = w + dw[i]
                if 0 <= nh < H and 0 <= nw < W and g[nh][nw] == '.':
                    g[nh][nw] = '#'
                    nextq.append([nh, nw])
                    cnt += 1
        q = nextq
    print(ans)
main()
### BUGGY CODE ###

import sys
import decimal
input=sys.stdin.readline


s=input()
CHECK=set()
ans=0
S=int(s)
for i in range(len(s)-1):
    
    temp=(S%pow(10,i+1))%2019
    if temp==0:
        ans+=1
    elif temp not in CHECK:
        CHECK.add(temp)
    else:
        ans+=1

print(ans)

### FIXED CODE ###


S=input()
s=[0 for i in range(len(S))]

for i in range(len(S)):
    s[i]=int(S[i])
CHECK=[0 for i in range(2021)]
ans=0
temp=0
for i in range(1,len(s)+1):
    #print(s[-i])
    temp=(temp+s[-i]*pow(10,i-1,2019)+2019*2)%2019
    #print(i,temp)
    #print(temp)
    CHECK[temp]+=1
for i in CHECK:
    ans+=i*(i-1)//2

ans+=CHECK[0]
 
print(ans)
### BUGGY CODE ###

from collections import deque
N,M,K = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]
friends = [set() for _ in range(N)]
blocks = [set() for _ in range(N)]
links = [set() for _ in range(N)]
searched = [0] * N
ans = [0] * N
d = deque()
for x, y in AB:
    friends[x-1].add(y-1)
    friends[y-1].add(x-1)
for x, y in CD:
    blocks[x-1].add(y-1)
    blocks[y-1].add(x-1)
for i in range(N):
    if searched[i]:
        continue
    trace = set()
    d.append(i)
    while d:
        temp = d.popleft()
        trace.add(temp)
        searched[temp] = 1
        for x in friends[temp]:
            if searched[x] == 0:
                d.append(x)
    for j in trace:
        ans[j] = len(trace) - 1 - len(trace&friends[j]) - len(trace&blocks[j])
print(*ans)

### FIXED CODE ###

from collections import deque
N,M,K = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]
friends = [set() for _ in range(N)]
blocks = [set() for _ in range(N)]
searched = [0] * N
ans = [0] * N
d = deque()
for x, y in AB:
    friends[x-1].add(y-1)
    friends[y-1].add(x-1)
for x, y in CD:
    blocks[x-1].add(y-1)
    blocks[y-1].add(x-1)
for i in range(N):
    if searched[i]:
        continue
    trace = set()
    d.append(i)
    trace.add(i)
    searched[i] = 1
    while d:
        temp = d.popleft()
        for x in friends[temp]:
            if searched[x] == 0:
                d.append(x)
                trace.add(x)
                searched[x] = 1
    chain = len(trace)
    for j in trace:
        ans[j] = chain - 1 - len(trace&friends[j]) - len(trace&blocks[j])
print(*ans)