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

N=int(input())
state=[]
for j in range(N):
    A=int(input())
    temp=[]
    for i in range(A):
        temp.append(tuple(map(int, input().split())))
    state.append(temp)


OK=[]
for i in range(2**N):
    conflict=0
    for person in range(N): #各人の発言を評価
        for one_state in state[person]:
            if ((i >> (one_state[0]-1)) & 1): #正直者に対して
                if (i >> person) & 1 and one_state[1] == 0:
                    conflict=1
            else: #不親切に対して
                if (i >> person) & 1 and one_state[1]==1:
                    conflict=1
    if conflict==0:
        OK.append(i)
#print(OK)

num=[]
for el in OK:
    count=0
    for j in range(N):
        if (el >> j) & 1:
            count+=1
    num.append(count)
#print(num)
print(max(num))



### FIXED CODE ###

N=int(input())
state=[]
for j in range(N):
    A=int(input())
    temp=[]
    for i in range(A):
        temp.append(tuple(map(int, input().split())))
    state.append(temp)


OK=[]
for i in range(2**N):
    conflict=0
    for person in range(N): #各人の発言を評価
        for one_state in state[person]:
            if ((i >> (one_state[0]-1)) & 1): #正直者に対して
                if (i >> person) & 1 and one_state[1] == 0:
                    conflict=1
            else: #不親切に対して
                if (i >> person) & 1 and one_state[1]==1:
                    conflict=1
    if conflict==0:
        OK.append(i)
#print(OK)

num=[]
for el in OK:
    count=0
    for j in range(N):
        if (el >> j) & 1:
            count+=1
    num.append(count)
#print(num)
print(max(num))
### BUGGY CODE ###

s = input()
n = len(s)
mod = 10**9 + 7
dp = [[0 for i in range(n)] for j in range(13)]

if s[0] == '?':
    for i in range(10):
        dp[i][0] = 1
else:
    dp[int(s[0])][0] = 1

mod_change_table = [(i*10)%13 for i in range(13)]

for x in range(1,len(s)):
    for y in range(13):
        if s[x]=='?':
            for j in range(10):
                dp[(mod_change_table[y]+j)%13][x] += dp[y][x-1]
        else:
            dp[(mod_change_table[y]+int(s[x]))%13][x] += dp[y][x-1]
            

print(dp[5][n-1] % mod)

### FIXED CODE ###

s = input()
mod = 10**9+7

# dp[逆順i桁][j mod 13] := 総数
dp = [[0]*13 for _ in range(len(s)+1)]
dp[0][0] = 1
mul = 1
s_rev = s[::-1]
for i in range(len(s)):
    x = s_rev[i]
    if x == '?':
        for k in range(10):
            for j in range(13):
                dp[i+1][(mul*k+j)%13] += dp[i][j]
                dp[i+1][(mul*k+j)%13] %= mod
    else:
        k = int(x)
        for j in range(13):
            dp[i+1][(mul*k+j)%13] += dp[i][j]
            dp[i+1][(mul*k+j)%13] %= mod
    mul = mul * 10 % 13

print(dp[len(s)][5] % mod)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
b = 0
for i in range(n):
    for j in range(i + 1,n):
        b += a[i]*a[j]
print(b%(10**9 + 7))


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7
s = sum(a)
ans = 0
for i in range(n):
    s -= a[i]
    ans += a[i]*s
    ans %= mod
print(ans)
### BUGGY CODE ###

import math

N,M = (int(i) for i in input().split())
a = [0] * M
mod = 1000000007
for i in range(M):
    a[i] = int(input())

def calc(f,t):
    tmp = t - f
    i = 1
    ans = 1
    if tmp == 1 or tmp == 0:
        return 1
    while(tmp >= 2*i):
        ans += math.factorial(tmp - i) // math.factorial(i) // math.factorial(tmp - 2*i)
        i += 1
    return ans

if M == 0:
    print(calc(0,N))
else:
    flag = 0

    A = calc(0,a[0]-1)

    for i in range(M-1):
        if a[i] + 1 == a[i+1]:
            flag = 1
            break
        A *= calc(a[i]+1,a[i+1]-1)
        A %= mod

    A *= calc(a[M-1]+1,N)
    A %= mod

    if flag == 1:
        print(0)
    else:
        print(A)


### FIXED CODE ###


N,M = (int(i) for i in input().split())
a = [0] * M
mod = 1000000007
for i in range(M):
    a[i] = int(input())
a.append(100000000)
flag = 0
for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        flag = 1
        break

dp = [1] * (N + 1)
tmp = 0

for i in range(N-1):
    if i+1 == a[tmp]:
        dp[i+2] = dp[i]
    elif i == a[tmp]:
        dp[i+2] = dp[i+1]
        tmp += 1
    else:
        dp[i+2] = (dp[i+1] + dp[i]) % mod

if flag == 1:
    print(0)
else:
    print(dp[N])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M, K = map(int, readline().split())
MOD = 998244353

def solve():
    m1pows = [1 for i in range(K + 1)]
    m1pows[0] = M * pow(M - 1, N - 1 - K, MOD) % MOD
    for i in range(1, K + 1):
        m1pows[i] = m1pows[i - 1] * (M - 1) % MOD
    cs = 1
    ans = 0
    for i in range(K + 1):
        ans += cs * m1pows[K - i]
        ans %= MOD
        cs *= (N - 1 - i) % MOD * pow(i + 1, MOD - 2, MOD) % MOD
    return ans


if __name__ == "__main__":
    print(solve())


### FIXED CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M, K = map(int, readline().split())
MOD = 998244353

def solve():
    m1pows = [1 for i in range(K + 1)]
    m1pows[0] = M * pow(M - 1, N - 1 - K, MOD) % MOD
    for i in range(1, K + 1):
        m1pows[i] = m1pows[i - 1] * (M - 1) % MOD
    cs = 1
    ans = 0
    for i in range(K + 1):
        ans += cs * m1pows[K - i]
        ans %= MOD
        cs *= (N - 1 - i) * pow(i + 1, MOD - 2, MOD)
        cs %= MOD
    return ans


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

from numba import jit
n = int(input())
a = []

while n%2 == 0:
    a.append(2)
    n //= 2

f = 3
while f**2 <= n:
    while n%f == 0:
        a.append(f)
        n //= f
    f += 2
if n != 1:
    a.append(n)

def cal(a):
    ans, num = 0, len(a)
    diff = float('inf')
    for i in range(2**num):
        b = ['-']*num
        c0, c1 = 1, 1
        for j in range(num):
            if ((i>>j)&1):
                b[num-1-j] = '+'
        for k in range(num):
            if b[k] == '+':
                c0 *= a[k]
            else:
                c1 *= a[k]
        if abs(c0-c1) < diff:
            ans = max(len(str(c0)), len(str(c1)))
            diff = abs(c0-c1)
    return ans
print(cal(a))


### FIXED CODE ###

n = int(input())
i, ans = 1, 0

while i**2 <= n:
    if n%i == 0:
        num = n//i
        ans = max(len(str(num)), len(str(i)))
    i += 1
print(ans)
### BUGGY CODE ###

import bisect
n , m = map(int, input().split())
a = list(map(int,input().split()))
a.sort()
for i in range(m):
    b , c = map(int, input().split())
    index = bisect.bisect_left(a,c)
    if index>b-1:
        a=a[b:index]+[c]*b+a[index:]
    else:
        a=[c]*index+a[index:]
print(sum(a))


### FIXED CODE ###

n , m = map(int, input().split())
a = list(map(int,input().split()))
a.sort()
bc=[]
for i in range(m):
    b , c = map(int, input().split())
    bc.append((b,c))
bc.sort(key = lambda x : x[1],reverse=True)

t=0
for i in range(m):
    b,c=bc[i]
    if t>=n:
        break
    if a[t]>=c:
        break
    for j in range(b):
        if a[t]<c:
            a[t]=c
            if t<n-1:
                t+=1
        else:
            break
print(sum(a))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
read = sys.stdin.read

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

n, m, s, t = map(int, input().split())
U, V, A, B = np.array(read().split(), dtype=np.int64).reshape(m, 4).T
csr_yen = csr_matrix((A, (U, V)), shape=(n+1, n+1))
csr_snuuk = csr_matrix((B, (U, V)), shape=(n+1, n+1))
G_yen = dijkstra(csr_yen, directed=False, indices=s)
G_snuuk = dijkstra(csr_snuuk, directed=False, indices=t)
L = np.zeros(n, dtype=np.int64)
U = 10**15
now = U
for i in range(n, 0, -1):
  now = min(now, int(G_yen[i]+G_snuuk[i]))
  L[i-1] = U-now
print(*L, sep="\n")

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import heapq

def dijkstra(n, start, edge):
    dist = [float("inf")]*n
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, v = heapq.heappop(que)
        if dist[v] < d:
            continue
        for nv, nd in edge[v]:
            if dist[nv] > d + nd:
                dist[nv] = d + nd
                heapq.heappush(que, (dist[nv], nv))
    return dist
    
n, m, s, t = map(int, input().split())
G_yen = [[] for _ in range(n+1)]
G_snuuk = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    G_yen[u].append((v, a))
    G_yen[v].append((u, a))
    G_snuuk[u].append((v, b))
    G_snuuk[v].append((u, b))
dijk_yen = dijkstra(n+1, s, G_yen)
dijk_snuuk = dijkstra(n+1, t, G_snuuk)
L = []
U = 10**15
now = U
for i in range(n, 0, -1):
    now = min(now, dijk_yen[i]+dijk_snuuk[i])
    L.append(U-now)
print(*L[::-1], sep="\n")
### BUGGY CODE ###

import math
N=int(input())
R=0

def gcd_3(a,b,c):
  return math.gcd(math.gcd(a,b), c)

for a in range(1,N+1):
  for b in range(1,N+1):
    for c in range(1,N+1):
      R+=gcd_3(a,b,c)

print(R)

### FIXED CODE ###

import math
N=int(input())
R=0

def gcd_3(a,b,c):
  return math.gcd(math.gcd(a,b), c)

for a in range(1,N+1):
  for b in range(1,N+1):
    for c in range(1,N+1):
      R+=gcd_3(a,b,c)

print(R)
### BUGGY CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum_(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, k = map(int, input().split())
ppp = list(map(int, input().split()))
pppa = []
for i in range(k):
    pppa += ppp
ppp = pppa
k = 1
bit = Bit(3000)
ans_ = 0

for i, p in enumerate(ppp):
    bit.add(p, 1)
    ans_ += i + 1 - bit.sum_(p)

mod = 10 ** 9 + 7
ans = (ans_ * k) % mod
ppp = sorted(ppp)

ppp_ = set(ppp)
dic1 = {}
dic2 = {}
for i in ppp_:
    dic1[i] = 0
    dic2[i] = 0

for i in ppp:
    dic1[i] += 1
    dic2[i] += 1

k_ = ((k-1) * k / 2) % mod
k_ = int(k_)
for i in ppp_:
    dic1[i] = 0
    ans += k_ * dic2[i] * sum(dic1.values())
    ans %= mod

print(ans)


### FIXED CODE ###

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

ans1 = 0
for i in range(n):
    for j in range(i+1, n):
        if a[i] > a[j]:
            ans1 += 1

ans2 = 0
for i in a:
    for j in a:
        if i > j:
            ans2 += 1

ans = k * ans1 + k * (k-1) // 2 * ans2
ans %= 10 ** 9 + 7

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

n,k = (int(x) for x in input().split())
if k>n:
    k = n
h_list = [int(i) for i in input().split()]

h_list.sort()
h_list.reverse()

for i in range(k):
    del h_list[0]

ans = sum(h_list)
print(ans)

### FIXED CODE ###

n,k = (int(x) for x in input().split())
if k>n:
    k = n
h_list = [int(i) for i in input().split()]

h_list.sort()

ans = sum(h_list[0:n-k])
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
ps=[list(input().split()) for _ in range(M)]

a=[]
w=[]
count=0

for j in range(M):
    if ps[j][1]=="WA":
        if ps[j][0] not in a:
            w.append(ps[j][0])
    elif ps[j][1]=="AC":
        if ps[j][0] not in a:
            a.append(ps[j][0])

for i in range(len(a)):
    count+=w.count(a[i])

print(len(a),count)

### FIXED CODE ###

N,M=map(int,input().split())

AC=[0]*N
WA=[0]*N
ac=0
wa=0

for i in range(M):
    p,s=map(str,input().split())
    P=int(p)
    if s=="AC":
        if AC[P-1]!=P:
            AC[P-1]+=P
            ac+=1
            wa+=WA[P-1]
    else:
        if AC[P-1]!=P:
            WA[P-1]+=1

print(ac,wa)
### BUGGY CODE ###

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

a.insert(0, 0)

#cnt = 0
#for i in range(n):
#    for j in range(n):
#        if i + 1 == a[j]:
#            cnt = cnt + 1

#    print(cnt)
#    cnt = 0

for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

import collections

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

c = collections.Counter(a)

a.insert(0, 0)

for i in range(n):
    print(c[i+1])
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline().strip()

n, d, a = map(int, input().split())

x = []
h = {} # x:h
for _ in range(n):
    i, j = map(int, input().split())
    x.append(i)
    h[i] = j
x.sort()

ans = 0
todo = [0 for _ in range(n)] #未処理は0、処理済は1
for i in range(n):
    if todo[i] == 0:
        if h[x[i]] % a == 0:
            k = h[x[i]] // a
        else:
            k = h[x[i]] // a + 1
        ans += k
        todo[i] = 1
        for j in range(i+1, n):
            if x[j] <= x[i] + 2*d:
                if todo[j] == 0:
                    if h[x[j]] <= a * k:
                        todo[j] = 1
                    else:
                        h[x[j]] -= a * k
            else:
                break

print(ans)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline().strip()

n, d, a = map(int, input().split())

x = []
h = {} # x:h
for _ in range(n):
    i, j = map(int, input().split())
    x.append(i)
    h[i] = j
x.sort()
x.append(x[-1] + 2*d + 1)

# attackで累積和を用いる
ans = 0
attack = [0 for _ in range(n+1)]
for i in range(n):
    attack[i] += attack[i-1]
    if attack[i] >= h[x[i]]:
        continue

    if (h[x[i]] - attack[i]) % a == 0:
        j = (h[x[i]] - attack[i]) // a
    else:
        j = (h[x[i]] - attack[i]) // a + 1
    attack[i] += a * j
    ans += j

    # 二分探索で、x[y] > x[i] + 2*d、を満たす最小のyを求める
    # start <= y <= stop
    start = i + 1
    stop = n
    k = stop - start + 1
    while k > 1:
        if x[start + k//2 - 1] <= x[i] + 2*d:
            start += k//2
        else:
            stop = start + k//2 - 1
        k = stop - start + 1
    attack[start] -= a * j

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

import sys
input = sys.stdin.readline

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

A=[list(map(int,input().split())) for i in range(H)]
B=[list(map(int,input().split())) for i in range(H)]


SA=[[0]*(W+1) for i in range(H+1)]

for i in range(H):
    for j in range(W):
        SA[i][j]=abs(A[i][j]-B[i][j])

DP=[[[] for i in range(W+1)] for i in range(H+1)]

DP[0][0]=[SA[0][0]]

MID=(H+W-2)//2

def next(i,j,t):
    if t<=MID:
        return [i+j,abs(i-j)]
    RET=[]
    lim=80*(MID-abs(t-MID)+2)
    if i+j<=lim:
        RET.append(i+j)

    if abs(i-j)<=lim:
        RET.append(abs(i-j))

    return RET

for i in range(H):
    for j in range(W):
        for k in set(DP[i][j]):
            DP[i+1][j].extend(next(k,SA[i+1][j],i+j))
            DP[i][j+1].extend(next(k,SA[i][j+1],i+j))
                
print(min(DP[H-1][W-1]))


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

A=[list(map(int,input().split())) for i in range(H)]
B=[list(map(int,input().split())) for i in range(H)]

SA=[[0]*W for i in range(H)]

for i in range(H):
    for j in range(W):
        SA[i][j]=abs(A[i][j]-B[i][j])

DP=[[0 for i in range(W)] for j in range(H)]

DP[0][0]=1<<(H+W)*80+SA[0][0]

for i in range(H):
    for j in range(W):
        tempbit=DP[i][j]
        if i+1<H:
            DP[i+1][j]|=tempbit<<SA[i+1][j]
            DP[i+1][j]|=tempbit>>SA[i+1][j]

        if j+1<W:
            DP[i][j+1]|=tempbit<<SA[i][j+1]
            DP[i][j+1]|=tempbit>>SA[i][j+1]

ANS=1<<30
for i in range((H+W)*160+1):
    if 1<<i & DP[-1][-1]!=0:
        ANS=min(ANS,abs(i-(H+W)*80))

print(ANS)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
l = list([list(map(int, input().split())) for _ in range(q)])

for i in l:
    l = i[0]
    r = i[1]
    print(s[l-1:r].count('AC'))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N+1)

for i in range(N):
    t[i+1] = t[i] + (1 if S[i: i+2] == 'AC' else 0)

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
cnt = 0
#Flag = True

for i in range(N-2):
  for j in range(i+1, N-1):
    k = j + 1
    while L[k-1] == L[k]:
      if k == N-1:
        k = j + 1
        break
      k += 1
    #print(i, j, k)
    cnt += bisect_left(L, L[i]+L[j]) - k
    #print(cnt)

print(cnt)

### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
cnt = 0

for i in range(N-2):
  for j in range(i+1, N-1):
    cnt += max(bisect_left(L, L[i]+L[j]) - (j+1), 0)

print(cnt)
### BUGGY CODE ###

N, K = map(int,input().split())
max=0
t=list(input().split())
for i in range(N-K+1):
    x=0
    for j in range(K):
        x+=int(t[i+j])
    if max<x :
        max=x
print((max+K)/2)


### FIXED CODE ###

N, K = map(int,input().split())
t=list(input().split())
s=[int(n) for n in t]
max=x=sum(s[:K])
for i in range(N-K):
    x+=(s[K+i]-s[i])
    if max<x :
        max=x
print((max+K)/2)
### BUGGY CODE ###

import heapq

N, Q = map(int, input().split())

event = []
for _ in range(N) :
    s, t, x = map(int, input().split())
    event.append([s - x, t - x, x])

D = [int(input()) for _ in range(Q)]

event.sort(key=lambda x: x[0])
closed = []

ei = 0

for d in D :
    while ei < N and event[ei][0] <= d :
        heapq.heappush(closed, (event[ei][2], event[ei][1]))
        ei += 1
    while len(closed) > 0 and closed[0][1] <= d :
        heapq.heappop(closed)
    
    if len(closed) == 0 :
        print(-1)
    else :
        print(closed[0][0])

### FIXED CODE ###

import sys, heapq
input = sys.stdin.readline

N, Q = map(int, input().split())

event = []
for _ in range(N) :
    s, t, x = map(int, input().split())
    event.append([s - x, t - x, x])

D = [int(input()) for _ in range(Q)]

event.sort()

closed = []
ei = 0

for d in D :
    while ei < N and event[ei][0] <= d :
        heapq.heappush(closed, (event[ei][2], event[ei][1]))
        ei += 1
    while closed and closed[0][1] <= d :
        heapq.heappop(closed)
    
    if closed :
        print(closed[0][0])
    else :
        print(-1)
### BUGGY CODE ###

n = int(input())
ans = 1
lst = list(map(int, input().split()))
for _ in lst:
    ans *= _

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

### FIXED CODE ###

n = int(input())
ans = 1
lst = list(map(int, input().split()))
flg = 0
if 0 in lst:
    print(0)
else:
    for _ in lst:
        ans *= _
        if ans > 10**18:
            print(-1)
            flg = 1
            break
    if not flg :
        print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
S = input()
ans = 0
# for i in range(len(S)-3):
i = 0
while i < len(S)-3:
    flag = False
    li = []
    # for j in range(i+4, len(S)+1):
    j = i+4
    while j < len(S)+1:
        if int(S[i:j]) % 2019 == 0:
            ans += 1
            li.append(j)
            j += j-i
            flag = True
        j += 1
    if flag:
        i += max(1, min(li)-5)
    else:
        i += 1

print(ans)


### FIXED CODE ###

s = input()[::-1]
length = len(s)
a = [0] * length
d = [0] * length
ans = [0] * 2019
x = 10

a[0] = int(s[0])
d[0] = a[0]
ans[d[0]] += 1

for i in range(1, length):
    a[i] = int(s[i]) * x % 2019
    d[i] = (d[i-1] + a[i]) % 2019
    ans[d[i]] += 1
    x = x * 10 % 2019

ans_c = [i for i in ans if i != 0]

print(int(sum([ans_c[i] * (ans_c[i]-1) for i in range(len(ans_c))]) / 2) + ans[0])
### BUGGY CODE ###

# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# import re
from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
S = input()
Slen = len(S)

if len(S)<=3:
    print(0)
    exit()

@lru_cache(maxsize=10000)
def check(n):
    if n%2019 == 0:
        return True
    else:
        return False

ans = 0
for i in range(Slen - 4 + 1):
    num_s = 4
    # for num_s in range(4,Slen+1-i):
    while num_s < Slen+1-i:
        num = int(S[i:i+num_s])
        if check(num):
            ans += 1
            num_s += 4
        else:
            num_s += 1
        # print(num,num_s,ans)

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


### FIXED CODE ###

# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# import re
from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
S = input()[::-1]

MOD = 2019
tmp = [0]*MOD
tmp[0] += 1
tens = 1
num = 0
for s in S:
    num += int(s) * tens
    num = num % MOD
    tmp[num] += 1
    tens *= 10
    tens %= MOD

ans = 0
for i in tmp:
    ans += i*(i-1)//2

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))
### BUGGY CODE ###

S = input()
Q = int(input())
hanten = 1
for _ in range(Q):
    q = list(map(str, input().split()))
    if q[0]=='1':
        hanten *= -1
    else:
        if hanten==1:
            if q[1]=='1':
                S = q[2] + S
            else:
                S = S + q[2]
        else:
            if q[1]=='1':
                S = S + q[2]
            else:
                S = q[2] + S

if hanten==1:
    print(S)
else:
    print(''.join(reversed(list(S))))

### FIXED CODE ###

S = input()
Q = int(input())
hanten = 1
front = []
back = []
for _ in range(Q):
    q = list(map(str, input().split()))
    if q[0]=='1':
        hanten *= -1
    else:
        if hanten==1:
            if q[1]=='1':
                front.append(q[2])
            else:
                back.append(q[2])
        else:
            if q[1]=='1':
                back.append(q[2])
            else:
                front.append(q[2])


if hanten==1:
    print(''.join(list(reversed(front)) + list(S) + back))
else:
    print(''.join(list(reversed(list(S)+back))+front))
### BUGGY CODE ###

S = input()
ans = 0
A = [0] * 2020
A[0] = 1
for i in range(len(S)):
     x = int(S[-i-1:]) % 2019
     A[x] += 1

while 0 in A:
    A.remove(0)

while 1 in A:
    A.remove(1)

for i in A:
    ans += int(i * (i-1) / 2)

print(ans)

### FIXED CODE ###

p=d=2019
z=[0]*p
for i,j in enumerate(input()[::-1]):
	d=d+int(j)*pow(10,i,p)
	z[d%p]+=1
r=z[0]
for i in z:
	r+=i*(i-1)//2
print(r)
### BUGGY CODE ###

N=int(input())
word=[]
word_lst=[]
for i in range(N):
  s=input()
  word.append(s)
  word_lst.append(list(word[i]))
  word_lst[i].sort()
  word_lst[i]=''.join(word_lst[i])

count=0
for i in range(N):
  for j in range(N):
    if word_lst[i]==word_lst[j]:
      count=count+1

total=int((count-N)/2)
  
  
print(total)  


### FIXED CODE ###

import collections

n=int(input())
s=[]
set={}
for i in range(n):
    s.append(input())
for i in range(n):
    temp=list(s[i])
    temp.sort()
    s[i]=''.join(temp)
count=0
ans=collections.Counter(s)
countlist=ans.most_common()
for i in range(len(countlist)):
    if countlist[i][1]<=1:
        break
    else:
        temp=countlist[i][1]-1
        count+=(temp+1)*temp//2

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

import sys
sys.setrecursionlimit(10**6)
N = int(input())
S = input()

ans = set()

def solve(c, idx):
    if len(c)==3:
        ans.add(c)
    if idx >= len(S):
        return
    solve(c+S[idx], idx+1)
    solve(c, idx+1)

if __name__ == "__main__":
    solve("", 0)
    print(len(ans))

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    cnt = 0
    n = str(i).zfill(3)
    for c in S:
        if c == n[cnt]:
            cnt += 1

        if cnt == 3:
            ans += 1
            break

print(ans)