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

s = list(input().rstrip())
n = len(s)
dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1

for i in range(n):
    c = -1 if s[i] == '?' else int(s[i])
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]
        for j in range(13):
            dp[i + 1][j] %= 10 ** 9 + 7
print(dp[n][5])


### FIXED CODE ###

s = list(input().rstrip())
n = len(s)
m = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1

for i in range(n):
    c = -1 if s[i] == '?' else int(s[i])
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]
        for j in range(13):
            dp[i + 1][j] %= m
print(dp[n][5])
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

N = int(input())
town = [[int(x) for x in input().split()] + [i] for i in range(N)]


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(dict)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src][dst] = weight

    def get_nodes(self):
        return self.graph.keys()


class Prim(object):
    """
    プリム法（二分ヒープ）による最小全域木
    O((E+V)logV)
    """

    def __init__(self, graph, start=0):
        self.edge = []
        self.total = 0

        g = graph.graph
        n = len(graph)
        visited = [False] * n
        visited[start] = True

        Q = []
        for v, cost in g[start].items():
            heappush(Q, (cost, (start, v)))

        while Q:
            cost, e = heappop(Q)

            if visited[e[1]]:
                continue

            self.edge.append(e)
            self.total += cost
            visited[e[1]] = True

            for v, cost in g[e[1]].items():
                heappush(Q, (cost, (e[1], v)))


def built(g, town):
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        dx = abs(t1[0] - t2[0])
        dy = abs(t1[1] - t2[1])
        c = min(dx, dy)
        g.add_edge(t1[2], t2[2], c)
        g.add_edge(t2[2], t1[2], c)
    return g


g = Graph()
g = built(g, sorted(town, key=itemgetter(0)))
g = built(g, sorted(town, key=itemgetter(1)))
p = Prim(g)
print(p.total)


### FIXED CODE ###

import sys
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

readline = sys.stdin.readline

N = int(readline())
town = [None] * N
for i in range(N):
    x, y = map(int, readline().split())
    town[i] = (i, x, y)

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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


def Kruskal(edges):
    edge = []
    total = 0

    uf = UnionFind(N)
    Q = sorted(edges, reverse=True)

    while len(edge) < N - 1 and Q:
        cost, e = Q.pop()
        if uf.find(e[0]) != uf.find(e[1]):
            total += cost
            edge.append(edge)
            uf.union(*e)
    return total


edges = []
for xy in [1, 2]:
    town = sorted(town, key=itemgetter(xy))
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        d = t2[xy] - t1[xy]
        edges.append((d, (t1[0], t2[0])))
print(Kruskal(edges))
### BUGGY CODE ###

import numpy as np
n, d = list(map(int, input().split()))
a = list(map(int, input().split()))

a = np.array(a)

e = a*0.5 + 0.5
ans = 0

for i in range(n-d+1):
  Sum = sum(e[i:i+d])
  
  if Sum >= ans:
    ans = Sum
  else:
    pass
  
print(ans)

### FIXED CODE ###

import numpy as np
n, d = list(map(int, input().split()))
a = list(map(int, input().split()))
Max = 0
Sum = 0
a = np.array(a)
a = a*0.5 + 0.5
ans = []

if d == 1:
  print(max(a))
elif n == d:
  print(sum(a))
else:
  for i in range(n-d+1):
    left = a[i]
    right = a[i+d-1]

    if i == 0:
      Sum = sum(a[i:i+d])
      Max = sum(a[i:i+d])
      ans = a[i:i+d]
    else:
      Sum = Sum + right - a[i-1]

      if Sum >= Max:
        Max = Sum
        ans = a[i:i+d]
      else:
        pass

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

S = input()
len_before = len(S)
for i in range(len_before):
  S_after = S.replace('01','').replace('10','')
  if '10' in S_after or '01' in S_after:
    S = S_after
  else:
    break
len_after = len(S_after)
print(len_before - len_after)

### FIXED CODE ###

S = input()
zero = S.count('0')
one = len(S) - zero
num = zero if zero <= one else one
print(num * 2)
### BUGGY CODE ###

import itertools
while 1:
	n = input()
	if n == 0: break
	s = sorted(map(int,raw_input().split()))
	sm1 = ans = sum(s)
	for i in range(1,n-1):
		for party in sorted(itertools.combinations(s,i), key = lambda x:sum(x)):
			sm2 = sm1 - 2*sum(party)
			if sm2 < -ans: break
			ans = min(ans,abs(sm2))
	print ans

### FIXED CODE ###

def S(i,x,y):
	if 2*x >= A: return 2*x-A
	if 2*y >= A: return 2*y-A
	return min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	A = sum(a)
	print S(1,a[0],0)
### BUGGY CODE ###

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

new_li = []
n = 0

while True:
  if li[1] == 1:
    print(0)
    break

  li[0] = abs(li[0]-li[1])
  new_li.append(li[0])
  
  if n>=2:
    if new_li[n] == new_li[n-2]:
      print(min(new_li))
      break
  n += 1

### FIXED CODE ###

x, k = map(int, input().split())

n = x%k

if n < abs(n-k):
  print(n)
else:
  print(abs(n-k))
### BUGGY CODE ###

#!/usr/bin/env python3

import sys

sys.setrecursionlimit(10**7)


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [read_h() if m > 1 else typ(input()) for _ in range(n)]


def main():
    N, = read_h()
    arr = sorted(read_h())

    cnt = 0
    for X in set(arr):
        tmp_cnt = 0
        for a in arr:
            if a > X + 1:
                break
            if X - 1 <= a <= X + 1:
                tmp_cnt += 1

        cnt = max(cnt, tmp_cnt)

    print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys

sys.setrecursionlimit(10**7)


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [read_h() if m > 1 else typ(input()) for _ in range(n)]


def main():
    N, = read_h()
    arr = read_h()

    from collections import Counter
    c = Counter(arr)

    cnt = 0
    for X in c.keys():
        cnt = max(cnt, c.get(X - 1, 0) + c.get(X, 0) + c.get(X + 1, 0))

    print(cnt)


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

import math
import collections
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    maxv = n*(n-1)//2
    a = [list(map(int, input().split())) for i in range(n)]
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
    v = 0
    Id = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if i < j:
                Id[i][j] = v
                v += 1

    def toId(i, j):
        if i > j:
            i, j = j, i
        return Id[i][j]

    to = [[] for i in range(maxv)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] = toId(i, a[i][j])
        for j in range(n - 2):
            to[a[i][j+1]].append(a[i][j])

    visited = [False for i in range(maxv)]
    calculated = [False for i in range(maxv)]
    dp = [0 for i in range(maxv)]

    def dfs(v):
        if visited[v]:
            if not calculated[v]:
                return -1
            return dp[v]
        visited[v] = True
        dp[v] = 1
        for u in to[v]:
            ret = dfs(u)
            if ret == -1:
                return -1
            dp[v] = max(dp[v], ret + 1)
        calculated[v] = True
        return dp[v]

    ans = 0
    for i in range(v):
        ret = dfs(i)
        if ret == -1:  # detected cycle
            print(-1)
            exit()
        ans = max(ans, ret)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
import collections
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    maxv = n*(n-1)//2
    a = [list(map(int, input().split())) for i in range(n)]
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
    v = 0
    Id = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if i < j:
                Id[i][j] = v
                v += 1

    def toId(i, j):
        if i > j:
            i, j = j, i
        return Id[i][j]

    to = [[] for i in range(maxv)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] = toId(i, a[i][j])
        for j in range(n - 2):
            to[a[i][j+1]].append(a[i][j])

    visited = [False for i in range(maxv)]
    calculated = [False for i in range(maxv)]
    dp = [0 for i in range(maxv)]

    def dfs(v):
        if visited[v]:
            if not calculated[v]:
                return -1
            return dp[v]
        visited[v] = True
        dp[v] = 1
        for u in to[v]:
            ret = dfs(u)
            if ret == -1:
                return -1
            dp[v] = max(dp[v], ret + 1)
        calculated[v] = True
        return dp[v]

    ans = 0
    for i in range(v):
        ret = dfs(i)
        if ret == -1:  # detected cycle
            print(-1)
            exit()
        ans = max(ans, ret)
    print(ans)


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

# -*- coding: utf-8 -*-
s = input()
q = int(input())

for i in range(q):
    query = input()
    if query == "1":
        s = s[::-1]
    else:
        q2 = query.split()
        if q2[1] == "1":
            s = q2[2]+s
        else:
            s = s + q2[2]
print(s)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import deque

s = list(input())
q = int(input())

a = deque(s)
reverse = False

for i in range(q):
    query = input()
    if query == "1":
        if reverse:
            reverse = False
        else:
            reverse = True
    else:
        x, q2_1, q2_2 = query.split()
        if q2_1 == "1":
            if reverse:
                a.append(q2_2)
            else:
                a.appendleft(q2_2)
        else:
            if reverse:
                a.appendleft(q2_2)
            else:
                a.append(q2_2)

s = list(a)
if reverse:
    s = s[::-1]
    print("".join(s))
else:
    print("".join(s))
### BUGGY CODE ###


def warshal_floyd(weights,N):
    d=[[weights[(i,j)] for i in range(N)] for j in range(N)]
    for i in range(N):
        d[i][i]=0
    for i in range(N):
        for j in range(N):
            for k in range(N):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d

def make_iteration(R,cities):
    S=[[c] for c in cities]
    iteration=[]
    while len(S)>0:
        v=S.pop()
        if len(v)!=len(set(v)):
            continue
        if len(v)==R:
            iteration.append(v)
        else:
            for c in cities:
                S.append(v+[c])
    return iteration

if __name__ == '__main__':
    N,M,R=list(map(int,input().split()))
    cities=list(map(int,input().split()))
    weights={(i,j):10**7 for i in range(N) for j in range(N)}
    #graph=[[10*7 for i in range(N)] for j in range(N)]
    for i in range(M):
        a,b,c=list(map(int,input().split()))
        a-=1
        b-=1
        weights[(a,b)]=min(weights[(a,b)],c)
        weights[(b,a)]=min(weights[(b,a)],c)
    d=warshal_floyd(weights,N)
    #d=floyd_warshall(weights)

    iteration=make_iteration(R,cities)
    mini_count=1e12
    for i in iteration:
        count=0
        for r in range(R-1):
            count+=d[i[r]-1][i[r+1]-1]
        mini_count=min(mini_count,count)
    print(mini_count)







### FIXED CODE ###

from itertools import permutations
def warshal_floyd(weights,N):
    d=weights
    for i in range(N):
        d[i][i]=0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d

if __name__ == '__main__':
    N,M,R=list(map(int,input().split()))
    cities=[r-1 for r in list(map(int,input().split()))]
    weights=[[1e10 for i in range(N)] for j in range(N)]
    for i in range(M):
        a,b,c=list(map(int,input().split()))
        a-=1
        b-=1
        weights[a][b]=c
        weights[b][a]=c

    d=warshal_floyd(weights,N)
    mini_count=1e12
    for c in permutations(cities):
        count=sum(d[i][j] for i,j in zip(c,c[1:]))
        mini_count=min(mini_count,count)
    print(mini_count)
### BUGGY CODE ###

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


def Gcd(a, b):
    while b:
        a, b = b, a%b
    return a


def gcd_list(num_list):
    for i, num in enumerate(num_list):
        if i == 0:
            g = num
        else:
            g = Gcd(num, g)
    return g

GCD = 0
for i in range(N):
    others = A[:]
    others.pop(i)
    gcd = gcd_list(others)
    if gcd > GCD:
        GCD = gcd
print(GCD)

### FIXED CODE ###

from fractions import gcd

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

GCD1 = []
g = A[0]
for a in A:
    g = gcd(g, a)
    GCD1.append(g)

B = A[::-1]
g = B[0]
GCD2 = []
for b in B:
    g = gcd(g, b)
    GCD2.append(g)

ans = 1
for i in range(N):
    if i == 0:
        a = GCD2[N-2]
    elif i == N-1:
        a = GCD1[N-2]
    else:
        a = gcd(GCD1[i-1], GCD2[N-i-2])
    ans = max(ans, a)
print(ans)
### BUGGY CODE ###

k, s = (int(i) for i in input().split())
count = 0

for i in range(k + 1):
    for j in range(k + 1):
        for k in range(k + 1):
            if i + j + k == s:
                count += 1

print(count)

### FIXED CODE ###

k, s = (int(i) for i in input().split())
count = 0

for h in range(k + 1):
    for i in range(k + 1):
        j = s - i - h
        if 0 <= j <= k:
            count += 1
print(count)
### BUGGY CODE ###

N = int(input())
nums = [int(e) for e in input().split()]
nums.sort()
t=1
ans = 1
for i in range(0,9):
    t = t*10
t+=7
if(N%2)==1:
    if(nums.count(0) == 1):
        for i in range(2,N,2):
            if(nums.count(i))==2:
                ans = ans * 2
            else:
                print('0')
                break
        else:
            print(ans%(t))
    else:
        print('0')
else:
    for i in range(1,N,2):
        if(nums.count(i))==2:
            ans = ans *2
        else:
            print('0')
            break
    else:
        print(ans%(t))

### FIXED CODE ###

N = int(input())
nums = [int(e) for e in input().split()]
nums.sort()
t=1
ans = 1
t = 10**9
t+=7
i=1
k=0
if(N%2)==1:
    if(nums.count(0) == 1):
        while(i<N):
            if nums[i] == nums[i+1]:
                i+=2
                ans = (ans *2)%t
                continue
            else:
                print('0')
                break
        else:
            print(ans)
    else:
        print('0')
else:
    while(k<N):
        if nums[k] == nums[k+1]:
            k += 2
            ans = (ans * 2)%t
            continue
        else:
            print('0')
            break
    else:
        print(ans)
### BUGGY CODE ###

n = int(input())

a = list(str(n))

ans = 0

for i in range(len(a)-3):
    for j in range(len(a)-3-i):
        k = a[i:i+4+j]
        if int("".join(map(str, k)))%2019 == 0:
            ans = ans + 1

print(ans)

### FIXED CODE ###

s = input()[::-1]
#sは文字列 逆向きにしている
sum_of_digits = 0

cnts = [0] * 2019

cnts[0] = 1

d = 1

for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10         #dを１０倍
    d %= 2019       #dを2019で割る（2019は10と素なので意味はないかも）
    cnts[sum_of_digits] += 1
    #cntは2019個ある　modの値が同じごとに個数を計算して足したもの

ans = 0
    
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2  
                    #cnt conbination 2
                    #mod ごとに m(m − 1)/2
        
#(i, j)が条件をみたすのはTi−1 == Tj (mod2019)のとき
#Ti−1 - Tj == 0 (mod2019) と等価 Ti−1 == Tj (mod2019)

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

S = input()
Q = int(input())
L = [list(map(str,input().split())) for i in range(Q)]

cnt = 0
FR = ""
BA = ""

for i in range(Q):
    if len(L[i]) == 1:
        cnt += 1
    else:
        if (int(L[i][1])+cnt)%2 == 0:
            BA = BA + L[i][2]
        else:
            FR = L[i][2]+FR

if cnt%2 == 0:
    print(FR+S+BA)
else:
    new_S = ''.join(list(reversed(FR+S+BA)))
    print(new_S)

### FIXED CODE ###

S = input()
Q = int(input())
L = [list(map(str,input().split())) for i in range(Q)]

cnt = 0
FR = ""
BA = ""

for i in range(Q):
    if len(L[i]) == 1:
        cnt += 1
    else:
        if (int(L[i][1])+cnt)%2 == 0:
            BA = BA + L[i][2]
        else:
            FR = L[i][2]+FR

if cnt%2 == 0:
    print(FR+S+BA)
else:
    new_S = ''.join(list(reversed(FR+S+BA)))
    print(new_S)
### BUGGY CODE ###

n = int(input()) 
t = [int(input()) for i in range(n)] 

res = [1]
i = 1

while i <= n:
  res.append(t[res[-1]-1])
  if res[-1] == 2:
    print(len(res)-1)
    break
  elif len(res) != len(set(res)):
    print(-1)
    break
  i += 1


### FIXED CODE ###

n = int(input()) 
t = [int(input()) for i in range(n)] 

x = 1
res = -1
for i in range(n):
  x = t[x-1]
  if x == 2:
    res = i + 1
    break
  
print(res)
### BUGGY CODE ###

n = int(input())
xx = list(map(int, input().split()))
 
for i in range(n):
  yy = xx[:i] + xx[i+1:]
  zz = sorted(yy)
  print(zz[(n-1)//2])

### FIXED CODE ###

n = int(input())
xx = list(map(int, input().split()))
yy = sorted(xx)

a = yy[n//2-1]
b = yy[n//2]

for x in xx:
  if x <= a:
    print(b)
  elif x >= b:
    print(a)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,M = map(int,input().split())
#低いやつを引いていく感じ
Hlist = list(int(x) for x in input().split())
delete_list = list()
d_append = delete_list.append

for i in range(M):
    A,B = map(int, input().split())
    if(Hlist[A-1] == Hlist[B-1]) :
        d_append(A-1)
        d_append(B-1)
    elif(Hlist[A-1] > Hlist[B-1]) :
        d_append(B-1)
    else :
        d_append(A-1)

delete_list = list(set(delete_list))#重複を消す
ans_list = Hlist.copy()
for d in delete_list:
    ans_list.remove(Hlist[d])

print(len(ans_list))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,M = map(int,input().split())
#低いやつを引いていく感じ
Hlist = list(int(x) for x in input().split())

flag = [1]*N

for i in range(M):
    A,B = map(int, input().split())
    A -= 1
    B -= 1
    if(Hlist[A] == Hlist[B]) :
        flag[A] = 0
        flag[B] = 0
    elif(Hlist[A] > Hlist[B]) :
        flag[B] = 0
    else :
        flag[A] = 0
print(sum(flag))
### BUGGY CODE ###

N,W = map(int,input().split())
WV = []
dp = [[0 for i in range(W+1)]for j in range(N+1)]
for i in range(N):
    WV.append(list(map(int,input().split())))
for i in range(N):
    dp[i+1][0:WV[i][0]] = dp[i][0:WV[i][0]]
    for w in range(WV[i][0],W+1):
        dp[i+1][w] = max(dp[i][w],dp[i][w - WV[i][0]]+WV[i][1])
print(max(max(dp)))


### FIXED CODE ###

import numpy as np
N,W = map(int,input().split())
dp = np.zeros(W+1,dtype=int)
for i in range(N):
    w,v = map(int,input().split())
    dp[w:W+1] = np.maximum(dp[0:W+1-w]+v,dp[w:W+1])
print(dp[-1])
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
S=-10**14
for i in range(N+1):
  b=a[0:N+i]
  c=a[N+i:3*N]
  b.sort(reverse=1)
  c.sort()
  B=0
  C=0
  for j in range(N):
    B+=b[j]
    C+=c[j]
  S=max(S,B-C)
print(S)

### FIXED CODE ###

import heapq
N=int(input())
a=list(map(int,input().split()))
earl=[]
late=[]
for i in range(N):
  heapq.heappush(earl,a[i])
  heapq.heappush(late,-a[2*N+i])
E=0
L=0
for i in range(N):
  E+=a[i]
  L-=a[2*N+i]
e=[E]*(N+1)
l=[L]*(N+1)
for i in range(N):
  e[i+1]=e[i]+a[N+i]-heapq.heappushpop(earl,a[N+i])
  l[N-1-i]=l[N-i]-a[2*N-1-i]-heapq.heappushpop(late,-a[2*N-1-i])

ans=e[N]+l[N]
for i in range(N):
  ans=max(ans,e[i]+l[i])
print(ans)
### BUGGY CODE ###

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

bamboos = []
for _ in range(N):
    l = int(input())
    bamboos.append(l)
    
ABC = [A, B, C]

import itertools
import sys

ans = sys.maxsize
executed = set()
for i in range(3, N+1):
    for bamboos_rearranged in itertools.permutations(bamboos, i):
        execute = ','.join(map(str,bamboos_rearranged))
        if execute in executed:
            continue
        else:
            executed.add(execute)
        #print(bamboos_rearranged)
        for j in range(1, len(bamboos_rearranged)):
            for k in range(j+1, len(bamboos_rearranged)):
                bamboos_abc = (bamboos_rearranged[:j], bamboos_rearranged[j:k], bamboos_rearranged[k:])
                cost = 0
                flag = True
                for n, b in enumerate(bamboos_abc):
                    cost += (len(b) - 1) * 10
                    cost += abs(ABC[n] - sum(b))
                    if cost >= ans:
                        flag = False
                        break
                if flag == True:
                    ans = min(ans, cost)
print(ans)
        
    

### FIXED CODE ###

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

bamboos = []
for _ in range(N):
    l = int(input())
    bamboos.append(l)
    
import copy

def dfs(i, bs):
    if i == len(bamboos):
        #print(bs)
        if not bs['A'] or not bs['B'] or not bs['C']:
            return []
        return [bs]
    ret = []
    tmp = copy.deepcopy(bs)
    tmp['A'].append(bamboos[i])
    ret.extend(dfs(i+1, tmp))
    tmp = copy.deepcopy(bs)
    tmp['B'].append(bamboos[i])
    ret.extend(dfs(i+1, tmp))
    tmp = copy.deepcopy(bs)
    tmp['C'].append(bamboos[i])
    ret.extend(dfs(i+1, tmp))
    tmp = copy.deepcopy(bs)
    tmp['D'].append(bamboos[i])
    ret.extend(dfs(i+1, tmp))
    
    return ret

ABC = {'A': A, 'B': B, 'C': C}
bs_comb = dfs(0, {'A':[],'B':[],'C':[],'D':[]})

import sys
ans = sys.maxsize
for bs in bs_comb:
    cost = 0
    for abc in ['A', 'B', 'C']:
        cost += (len(bs[abc]) - 1) * 10
        cost += abs(sum(bs[abc]) - ABC[abc])
    ans = min(ans, cost)
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
for _ in range(Q):
  a, *b = input().split()
  if a=="1":
    S = S[::-1]
  else:
    if b[0] == "1":
      S = b[1] + S
    else:
      S += b[1]
print (S)

### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())
f = 0
for _ in range(Q):
  a, *b = input().split()
  f += int(a)
  if a == "2":
    if (int(b[0]) + f) % 2 == 1 :
      S.appendleft(b[1])
    else:
      S.append(b[1])
D = list(S)
print ("".join(D) if f % 2 == 0 else "".join(D[::-1]))
### BUGGY CODE ###

S = input()

modList = [0] * 2019 # あまりは0～2018の2019個

ans = 0

modList[0] = 1 # 解答でいうT(n)=0 の場合

# 最大20万回ループ、時間かかるならＤＰする？
for i in range(len(S)):
    m = int(S[i:]) % 2019
    modList[m] += 1

#print(modList)

for j in modList:
    if j <= 1:
        continue
    else:
        ans += j*(j-1)/2

print(int(ans))

### FIXED CODE ###

S = input()

modList = [0] * 2019 # あまりは0～2018の2019個

ans = 0

modList[0] = 1 # 解答でいうT(n)=0 の場合

# 最大20万回ループ、時間かかるならＤＰする？
# ↓ではTLEになった
# for i in range(len(S)):
#     m = int(S[i:]) % 2019
#     modList[m] += 1

# ↓　これでもTLEになった
# T = 0
# for i in range(1,len(S)+1):
#     # T += int(S[-i]) * 10**i
#     T += int(S[-i]) * ((10**i) % 2019)
#     modList[T % 2019] +=1

T = 0
a = 1
for s in S[::-1]:
    T = T+int(s) * a
    modList[T%2019]+=1
    a*=10
    a%=2019
#print(modList)

for j in modList:
    if j <= 1:
        continue
    else:
        ans += j*(j-1)/2

print(int(ans))