AtCoder Beginner Contest 164 - Multiple of 2019

Given is a string S consisting of digits from 1 through 9.
Find the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the following condition:
Condition: In base ten, the i-th through j-th characters of S form an integer that is a multiple of 2019.

-----Constraints-----
 - 1 ≤ |S| ≤ 200000
 - S is a string consisting of digits from 1 through 9.

-----Input-----
Input is given from Standard Input in the following format:
S

-----Output-----
Print the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the condition.

-----Sample Input-----
1817181712114

-----Sample Output-----
3

Three pairs - (1,5), (5,9), and (9,13) - satisfy the condition.

Source: atcoder | Difficulty: MEDIUM


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


S = input()
mc = [0] * 2019
tg = 0
digit = 1
for s in S[::-1]:
	tg += int(s) * digit
	mc[tg % 2019] += 1
	digit = digit * 10 % 2019
ans = sum((m * (m - 1) // 2 for m in mc))
print(ans + mc[0])


S = input()
X = [0] * 2019
X[0] = 1
d = 1
a = 0
for s in reversed(S):
	a = ((ord(s) - ord('0')) * d + a) % 2019
	d = d * 10 % 2019
	X[a] += 1
ans = sum((x * (x - 1) // 2 for x in X))
print(ans)


s = input()
n = len(s)
mod = 2019
t = [0] * n
dp = [0] * 2020
t[0] = int(s[-1])
dp[t[0]] += 1
for i in range(n - 1):
	t[i + 1] = t[i] + int(s[-2 - i]) * pow(10, i + 1, mod)
	t[i + 1] %= mod
	dp[t[i + 1]] += 1
ans = 0
for D in dp[1:]:
	ans += D * (D - 1) // 2
print(ans + (dp[0] + 1) * dp[0] // 2)


from collections import Counter
S = input()[::-1]
MOD = 2019
X = [0]
for (i, s) in enumerate(S):
	X.append((X[-1] + int(s) * pow(10, i, MOD)) % MOD)
C = Counter(X)
print(sum([v * (v - 1) // 2 for v in C.values()]))


S = input()
(ans, n) = (0, len(S))
dp = [0] * 2019
(s, dp[0], k) = (0, 1, 1)
for i in S[::-1]:
	s = (s + int(i) * k) % 2019
	k = k * 10 % 2019
	ans += dp[s]
	dp[s] += 1
print(ans)


M = 2019
t = 1
p = r = 0
c = [0] * M
for x in '0' + input()[::-1]:
	p += int(x) * t
	p %= M
	t = t * 10 % M
	r += c[p]
	c[p] += 1
print(r)


string = input()
length = len(string)
mod = [1] + [0] * 2018
s = 0
for i in range(length):
	s = (s + int(string[-1 - i]) * pow(10, i, 2019)) % 2019
	mod[s] += 1
print(sum([i * (i - 1) // 2 for i in mod]))


S = input()[::-1]
l = len(S)
t = 0
p = 0
ss = [0] * 2019
ss[0] = 1
d = 1
for i in S:
	p = (p + int(i) * d) % 2019
	d *= 10
	d %= 2019
	ss[p] += 1
for c in ss:
	t += c * (c - 1) // 2
print(t)


m = 2019
l = [0] * m
a = b = 0
k = 1
for c in input():
	l[b % m] += 1
	b -= int(c) * k
	a += l[b % m]
	k = k * 202 % m
print(a)


N = str(input())
(n, mods) = (0, [1] + [0] * 2018)
d = 1
for i in reversed(N):
	n = (n + int(i) * d) % 2019
	mods[n] += 1
	d = d * 10 % 2019
print(sum([i * (i - 1) // 2 for i in mods]))


import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict

def main():
	s = tuple(map(int, input()))
	lens = len(s)
	d1 = defaultdict(int)
	ss = 0
	num10 = 1
	for se in s[::-1]:
		ss += int(se) * num10 % 2019
		ss = ss % 2019
		d1[ss] += 1
		num10 = num10 * 10 % 2019
	r = d1[0]
	for v in d1.values():
		r += v * (v - 1) // 2
	print(r)

def __starting_point():
	main()
__starting_point()


from collections import Counter
S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
	t = int(s) % mod
	r += t * d
	r %= mod
	d = d * 10 % mod
	p[r] += 1
print(sum([i * (i - 1) // 2 for i in p]))


from collections import Counter
s = input()
n = len(s)
ans = 0
arr = [0] * (n + 1)
if s == '0':
	print(1)
	return
elif n == 1:
	print(0)
	return
for i in reversed(range(n)):
	arr[i] = (arr[i + 1] + int(s[i]) * pow(10, n - i - 1, 2019)) % 2019
m = Counter(arr)
for j in m.keys():
	ans += m[j] * (m[j] - 1) // 2
print(ans)


s = input()[::-1]
mod = [0] * 2019
mod[0] = 1
x = 1
num = 0
ans = 0
for t in s:
	num += int(t) * x
	num %= 2019
	x *= 10
	x %= 2019
	mod[num] += 1
for u in mod:
	ans += u * (u - 1) // 2
print(ans)


S = input()
P = 2019
ans = 0
count = [0] * P
count[0] = 1
u = 0
for (i, s) in enumerate(reversed(S)):
	u = (int(s) * pow(10, i, P) + u) % P
	ans += count[u]
	count[u] += 1
print(ans)


s = input()[::-1]
n = len(s)
cnt = [0] * 2020
res = 0
t = 0
p = 1
for c in s:
	c = int(c)
	t = (t + c * p) % 2019
	p = p * 10 % 2019
	cnt[t] += 1
res += (cnt[0] + 1) * cnt[0] // 2
for i in cnt[1:]:
	res += i * (i - 1) // 2
print(res)


s = input()
s = s[::-1]
m = [0] * 2019
m[0] = 1
a = 0
d = 1
ans = 0
for si in s:
	a = (a + int(si) * d) % 2019
	d = d * 10 % 2019
	ans += m[a]
	m[a] += 1
print(ans)


m = 2019
C = [0] * m
C[0] = 1
s = list(input())
now = 0
cnt = 0
while s:
	now += pow(10, cnt, m) * int(s.pop())
	now %= m
	C[now] += 1
	cnt += 1
ans = 0
for c in C:
	ans += c * (c - 1) // 2
print(ans)


mod = [0]
pw = 1
for c in input()[::-1]:
	mod.append((int(c) * pw + mod[-1]) % 2019)
	pw = pw * 10 % 2019
from collections import *
print(sum((v * (v - 1) // 2 for v in Counter(mod).values())))


s = input()[::-1]
ans = 0
u = 0
d = 1
l = [0] * 2019
l[0] = 1
for i in map(int, s):
	u = (u + i * d % 2019) % 2019
	l[u] += 1
	d = d * 10 % 2019
for i in l:
	ans += i * (i - 1) // 2
print(ans)


S = input()
dp = [0] * 2019
c = 0
dp[0] = 1
p = 0
q = 1
for i in range(len(S)):
	p += int(S[len(S) - 1 - i]) * q
	p %= 2019
	q *= 10
	q %= 2019
	dp[p] += 1
for j in dp:
	c += j * (j - 1) // 2
print(c)


s = input()
p = 2019
t = 1
y = 0
c = [0] * p
c[0] = 1
for x in map(int, s[::-1]):
	y = (y + t * x) % p
	c[y] += 1
	t = t * 10 % p
print(sum((i * (i - 1) // 2 for i in c)))


s = input()
a = len(s)
b = a - 4
c = 0
mod = 2019
num = [0] * mod
num[0] = 1
now = 0
ans = 0
_10 = 1
for i in range(a - 1, -1, -1):
	now = (now + int(s[i]) * _10) % mod
	_10 *= 10
	_10 %= mod
	ans += num[now]
	num[now] += 1
print(ans)


s = input()
n = len(s)
m = 2019
a = 0
r = [0 for _ in range(m + 1)]
r[0] = 1
z = 0
for i in range(0, n):
	z = (int(s[n - i - 1]) * pow(10, i, m) + z) % m
	a += r[z]
	r[z] += 1
print(a)


a = [1] + [0] * 2018
(s, p) = (0, 1)
for c in reversed(input()):
	s = (s + p * int(c)) % 2019
	p = p * 10 % 2019
	a[s] += 1
print(sum((x * (x - 1) // 2 for x in a)))


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce

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

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))

def ZIP(n):
	return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
S = list(map(int, list(input())))[::-1]
l = [0] * 2019
l[0] = 1
tmp = 0
z = 1
for (i, s) in enumerate(S):
	tmp += s * z
	z = z * 10 % 2019
	l[tmp % 2019] += 1
ans = 0
for v in l:
	ans += v * (v - 1) // 2
print(ans)


import numpy as np
from collections import Counter
YEAR = 2019

def solve(S: str):
	mod_year = np.arange(1, 10)
	mod_s = []
	for Si in map(int, reversed(S)):
		mod_s.append(mod_year[Si - 1])
		mod_year = mod_year * 10 % YEAR
	cum_sum = 0
	cum_sums = [cum_sum]
	for x in mod_s:
		cum_sum = (cum_sum + x) % YEAR
		cum_sums.append(cum_sum)
	answer = 0
	for (_, num) in list(Counter(cum_sums).items()):
		answer += num * (num - 1) // 2
	return answer

def main():
	S = input().strip()
	answer = solve(S)
	print(answer)

def __starting_point():
	main()
__starting_point()


M = 2019
s = input()[::-1]
a = t = 0
p = 1
l = [0] * M
for i in s:
	l[t] += 1
	t += int(i) * p
	t %= M
	a += l[t]
	p = p * 10 % M
print(a)


from collections import *
s = input()
p = 2019
c = Counter()
c[0] += 1
v = r = 0
k = 1
for i in s[::-1]:
	v += int(i) * k
	v %= p
	r += c[v]
	c[v] += 1
	k *= 10
	k %= p
print(r)


S = [int(a) for a in input()[::-1]]
m = 2019
N = len(S)
s = 0
p = 1
X = [0] * 2019
X[0] = 1
ans = 0
for a in S:
	s = (s + a * p) % m
	ans += X[s]
	X[s] += 1
	p = p * 10 % m
print(ans)


def main():
	(n, d, mods) = (0, 1, [1] + [0] * 2019)
	for i in reversed(input()):
		n = (n + int(i) * d) % 2019
		d = d * 10 % 2019
		mods[n] += 1
	print(sum([i * (i - 1) // 2 for i in mods]))
main()


S = input()
k = [0] * 2019
t = 0
k[0] = 1
for (i, s) in enumerate(S[::-1]):
	t += int(s) * pow(10, i, 2019)
	t %= 2019
	k[t] += 1
ans = 0
for l in k:
	ans += l * (l - 1) // 2
print(ans)


counter = [0] * 2019
counter[0] = 1
S = input()
tmp = 0
MOD = 2019
t = 1
for i in range(1, len(S) + 1):
	tmp += int(S[-i]) * t
	tmp %= MOD
	t *= 10
	t %= MOD
	counter[tmp] += 1
print(sum((i * (i - 1) // 2 for i in counter)))


S = input()[::-1]
n = len(S)
cnt = [0] * 2019
cnt[0] = 1
m = 0
d = 1
for i in S:
	m += int(i) * d
	m %= 2019
	cnt[m] += 1
	d *= 10
	d %= 2019
ans = 0
for i in cnt:
	ans += int(i * (i - 1) / 2)
print(ans)


s = input()
n = len(s)
a = 0
t = 1
d = [1] + [0] * 2018
for i in range(n):
	a += int(s[n - 1 - i]) * t
	a %= 2019
	t *= 10
	t %= 2019
	d[a] += 1
ans = 0
for i in d:
	ans += i * (i - 1) // 2
print(ans)


s = input()[::-1]
m = [0] * 2019
m[0] = 1
d = 1
t = 0
for i in s:
	t += int(i) * d
	t %= 2019
	m[t] += 1
	d = d * 10 % 2019

def c2(n):
	return n * (n - 1) // 2
print(sum([c2(i) for i in m]))


d = {0: 1}
(s, p) = (0, 1)
for c in reversed(input()):
	s = (s + p * int(c)) % 2019
	d[s] = d.get(s, 0) + 1
	p = p * 10 % 2019
print(sum((x * (x - 1) // 2 for x in d.values())))


S = input()
N = len(S)
q = [0]
count = [0 for i in range(2019)]
ans = 0
count[0] = 1
m10 = 1
for i in range(1, N + 1):
	a = int(S[-i])
	q.append((a * m10 + q[i - 1]) % 2019)
	m10 *= 10
	m10 %= 2019
	count[q[-1]] += 1
for i in range(2019):
	c = count[i]
	ans += c * (c - 1) // 2
print(ans)


import sys
from decimal import Decimal
import math
from itertools import combinations, product
import bisect
from collections import Counter, deque, defaultdict
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.141592653589793

def read_str():
	return sys.stdin.readline().strip()

def read_int():
	return int(sys.stdin.readline().strip())

def read_ints():
	return map(int, sys.stdin.readline().strip().split())

def read_str_list():
	return list(sys.stdin.readline().strip().split())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def lcm(a: int, b: int) -> int:
	return a * b // math.gcd(a, b)
import numpy as np

def Main():
	s = read_str()
	dp = np.zeros(2019, dtype=np.int64)
	dp[0] = 1
	cur = 0
	digit = 1
	for i in reversed(s):
		cur = (cur + int(i) * digit) % 2019
		dp[cur] += 1
		digit = digit * 10 % 2019
	print(np.sum([x * (x - 1) // 2 for x in dp]))
Main()


s = input()
n = len(s)
mod = 2019
d = 0
p = 1
ml = [0] * mod
for i in range(1, n + 1):
	k = int(s[-i])
	d += p * k
	d %= mod
	ml[d] += 1
	p *= 10
	p %= mod
ans = 0
for i in ml:
	ans += i * (i - 1) // 2
print(ans + ml[0])


def main():
	import collections
	S = input()
	mod_list = [0]
	for i in range(len(S)):
		index = len(S) - i - 1
		num = int(S[index])
		mod_list.append((mod_list[-1] + num * pow(10, i, 2019)) % 2019)
	CTR_mod_list = collections.Counter(mod_list).most_common()
	cnt = 0
	for i in range(len(CTR_mod_list)):
		n = CTR_mod_list[i][1]
		if n == 1:
			break
		cnt += n * (n - 1) // 2
	print(cnt)

def __starting_point():
	main()
__starting_point()


S = input()
S = S[::-1]
result = 0
t = [0] * 2019
m = 1
n = 0
for i in range(len(S)):
	t[n] += 1
	n += int(S[i]) * m
	n %= 2019
	result += t[n]
	m *= 10
	m %= 2019
print(result)


from collections import Counter
S = input()
P = [0] * (len(S) + 1)
mod = 2019
d = 1
for i in range(len(S), 0, -1):
	P[i - 1] = int(S[i - 1]) * d + P[i]
	P[i - 1] = P[i - 1] % mod
	d *= 10
	d = d % mod
P = Counter(P)
ans = 0
for p in P.values():
	ans += p * (p - 1) // 2
print(ans)


s = input()
mod = 2019
dp = [0] * mod
k = 0
t = 1
for x in map(int, s[::-1]):
	k += t * x
	k %= mod
	dp[k] += 1
	t *= 10
	t %= mod
print(sum((i * (i - 1) // 2 for i in dp)) + dp[0])


S = list(map(int, input()[::-1]))
R = [0]
r = 0
k = 1
for c in S:
	r = (r + k * c) % 2019
	k = k * 10 % 2019
	R.append(r)
N = [0] * 2019
ans = 0
for r in R:
	ans += N[r]
	N[r] += 1
print(ans)


from collections import Counter
S = list(map(int, list(input())))
A = [0]
for (i, s) in enumerate(S[::-1]):
	A.append((A[-1] + s * pow(10, i, 2019)) % 2019)
print(sum([v * (v - 1) // 2 for v in list(Counter(A).values())]))


s = input()
n = len(s)
c = [0] * 2019
c[0] += 1
t = 0
digit = 1
for ss in s[::-1]:
	t = (t + int(ss) * digit) % 2019
	digit = digit * 10 % 2019
	c[t] += 1
ans = 0
ans = sum((cc * (cc - 1) // 2 for cc in c))
print(ans)


S = list(map(int, list(input())))
S.reverse()
a = [0] * len(S)
y = 2019
x = 1
t = 0
cnt = [0] * y
res = 0
for i in range(len(S)):
	cnt[t] += 1
	t += S[i] * x
	t %= y
	res += cnt[t]
	x = x * 10 % y
print(res)


mod = 2019
a = input()
N = len(a)
t = [0] * mod
t[0] = 1
w = 1
u = 0
for i in range(N):
	u = int(a[N - 1 - i]) * w + u
	v = u % mod
	t[v] += 1
	w *= 10
	w %= mod
ans = 0
for i in t:
	ans += (i - 1) * i // 2
print(ans)


s = input()[::-1]
alist = [0] * 2019
num1 = 0
num2 = 1 / 10
lens = len(s)
for i in range(lens):
	num2 = int(num2 * 10 % 2019)
	num1 = (num1 + int(s[i]) * num2) % 2019
	alist[num1] += 1
alist[0] += 1
ans = 0
for i in range(2019):
	ans += alist[i] * (alist[i] - 1) // 2
print(ans)


from collections import Counter
S = input()
rlist = [0]
for i in range(len(S)):
	rlist.append((rlist[-1] + int(S[-i - 1]) * pow(10, i, 2019)) % 2019)
c = Counter(rlist)
c[0] -= 1

def nC2(n):
	return n * (n - 1) // 2
ans = c[0]
for k in c.keys():
	if c[k] >= 2:
		ans += nC2(c[k])
print(ans)


s = input()
a = 0
now = 1
l = [0] * 2019
for i in list(s)[::-1]:
	a = (a + now * int(i)) % 2019
	l[a] += 1
	now *= 10
	now %= 2019
ans = 0
for i in l:
	ans += (i - 1) * i // 2
print(ans + l[0])


s = input()
MOD = 2019
d = [0] * MOD
d[0] = 1
r = 0
t = 1
for i in reversed(s):
	r += int(i) * t
	r %= MOD
	t *= 10
	t %= MOD
	d[r] += 1
print(sum((i * (i - 1) // 2 for i in d)))


(a, *d) = [0] * 2020
for i in map(int, input()):
	p = [0] * 2019
	for j in range(2019):
		p[(j * 10 + i) % 2019] += d[j]
	d = p
	d[i] += 1
	a += d[0]
print(a)


s = input()
mod = [0] * 2019
mod[0] = 1
d = 1
n = 0
for i in reversed(s):
	n += int(i) * d
	n %= 2019
	d *= 10
	d %= 2019
	mod[n % 2019] += 1
print(sum((i * (i - 1) // 2 for i in mod)))


a = [int(c) * pow(10, i, 2019) % 2019 for (i, c) in enumerate(reversed(input()))]
s = [0]
for x in a:
	s += [(s[-1] + x) % 2019]
(cnt, ans) = ([0] * 2019, 0)
for x in s:
	ans += cnt[x]
	cnt[x] += 1
print(ans)


(M, a, t) = (2019, 0, 0)
l = [0] * M
for (i, c) in enumerate(input()[::-1]):
	l[t] += 1
	t += int(c) * pow(10, i, M)
	t %= M
	a += l[t]
print(a)


s = input()[::-1]
n = len(s)
cnts = [0] * 2019
cnts[0] = 1
num = 0
for i in range(n):
	num += int(s[i]) * pow(10, i, 2019)
	num %= 2019
	cnts[num] += 1
ans = 0
for cnt in cnts:
	ans += cnt * (cnt - 1) // 2
print(ans)


from collections import Counter
MOD = 2019
S = input()[::-1]
n = 0
x = 1
c = Counter()
ans = 0
for s in S:
	c[n] += 1
	n += int(s) * x
	n %= MOD
	ans += c[n]
	x = x * 10 % MOD
print(ans)


M = 2019
a = i = 0
d = [1] + [0] * M
p = 1
for j in input()[::-1]:
	i = (i + int(j) * p) % M
	a += d[i]
	d[i] += 1
	p = p * 10 % M
print(a)


def main():

	def modpow(x, n, mod):
		res = 1
		while n:
			if n % 2:
				res *= x % mod
			x *= x % mod
			n >>= 1
		return res
	s = input()
	s = s[::-1]
	s_len = len(s)
	mod = 2019
	d = [0] * mod
	d[0] = 1
	rev_num = 0
	for i in range(s_len):
		rev_num += int(s[i]) * int(modpow(10, i, mod))
		rev_num %= mod
		d[rev_num] += 1
	print(sum((i * (i - 1) // 2 for i in d)))

def __starting_point():
	main()
__starting_point()


import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import Counter

def main():
	s = input()
	n = len(s)
	amari = [0] * n
	ketaamari = 1
	t = 0
	for i1 in range(n):
		t = (t + ketaamari * int(s[-i1 - 1])) % 2019
		amari[-i1 - 1] = t
		ketaamari = ketaamari * 10 % 2019
	amari.append(0)
	ac = Counter(amari)
	r = 0
	for v in ac.values():
		r += v * (v - 1) // 2
	print(r)

def __starting_point():
	main()
__starting_point()


import sys
import collections

def resolve(in_):
	s = next(in_).strip()
	mod = 2019
	dp = [0] * (len(s) + 1)
	ch0 = ord(b'0')
	for (i, b) in enumerate(reversed(s), 1):
		dp[i] = (dp[i - 1] + (b - ch0) * pow(10, i, mod)) % mod
	return sum((v * (v - 1) // 2 for v in list(collections.Counter(dp).values())))

def main():
	answer = resolve(sys.stdin.buffer)
	print(answer)

def __starting_point():
	main()
__starting_point()


S = input()
cs = [0]
r = 1
for c in S[::-1]:
	cs.append((cs[-1] + r * int(c)) % 2019)
	r *= 10
	r %= 2019
from collections import Counter
ctr = Counter(cs)
ans = 0
for v in ctr.values():
	ans += v * (v - 1) // 2
print(ans)


s = input()
res = 0
m = 1
p = [0] * 2019
for i in map(int, s[::-1]):
	res += i * m
	res %= 2019
	p[res] += 1
	m *= 10
	m %= 2019
print(p[0] + sum([i * (i - 1) // 2 for i in p]))


ss = input().rstrip()
x = 1
y = 0
mod = [0] * 3000
ans = 0
mod[0] = 1
for i in range(len(ss)):
	s = ss[i * -1 - 1]
	n = int(s)
	y = (y + x * n) % 2019
	ans += mod[y]
	mod[y] += 1
	x = x * 10 % 2019
print(ans)


S = input()
mod = 2019
ctr = [0] * mod
t = 0
for (i, v) in enumerate(reversed(S)):
	t = (t + int(v) * pow(10, i, mod)) % mod
	ctr[t] += 1
ans = ctr[0]
for v in ctr:
	ans += v * (v - 1) // 2
print(ans)


from collections import Counter

def main():
	S = input()
	A = [0] * ((n := len(S)) + 1)
	A[1] = (a := int(S[-1])) % 2019
	for i in range(2, n + 1):
		a += pow(10, i - 1, 2019) * int(S[-i])
		A[i] = a % 2019
	c = Counter(A)
	ans = 0
	for v in list(c.values()):
		ans += v * (v - 1) // 2
	print(ans)

def __starting_point():
	main()
__starting_point()


from itertools import accumulate
from collections import Counter

def solve(n):
	return n * (n - 1) // 2
s = input()[::-1]
MOD = 2019
rest = []
for (i, x) in enumerate(s):
	if i == 0:
		tmp = 1
	else:
		tmp = tmp * 10 % MOD
	rest.append(int(x) * tmp % MOD)
result = [x % MOD for x in list(accumulate(rest))]
zero = result.count(0)
c = Counter(result)
c = list(c.values())
print(sum([solve(x) for x in c if x >= 2]) + zero)


(s, l) = (input(), 2019)
(m, a) = ([1] + [0] * l, 0)
for (i, e) in enumerate(s[::-1]):
	a += int(e) * pow(10, i, l)
	m[a % l] += 1
print(sum(map(lambda x: int(x * (x - 1) / 2), m)))


M = 2019
s = input()
(tot, ten, ans) = (0, 1, 0)
cnt = [0] * M
for si in s[::-1]:
	cnt[tot] += 1
	tot += int(si) * ten
	tot %= M
	ans += cnt[tot]
	ten *= 10
	ten %= M
print(ans)


import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter

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

def mp():
	return map(int, input().split())

def lmp():
	return list(map(int, input().split()))
s = input()[::-1]
n = len(s)
a = [0] * 2019
a[0] = 1
(c, d) = (0, 1)
for i in s:
	c += int(i) * d
	c %= 2019
	d *= 10
	d %= 2019
	a[c] += 1
ans = 0
for i in a:
	ans += i * (i - 1) // 2
print(ans)


s = input()
MOD = 2019
a = [0] * MOD
a[0] = 1
c_ = 0
ans = 0
t = 1
for i in reversed(s):
	c = (c_ + int(i) * t) % MOD
	a[c] += 1
	t *= 10
	t %= MOD
	c_ = c
for i in a:
	ans += i * (i - 1) // 2
print(ans)


(s, n, ans) = (input(), 0, 0)
mods = [0] * 2019
mods[0] = 1
for (i, j) in enumerate(reversed(s)):
	n = (n + int(j) * pow(10, i, 2019)) % 2019
	mods[n] += 1
for i in mods:
	ans += i * (i - 1) // 2
print(ans)


import math, itertools, fractions, heapq, collections, bisect, sys, queue, copy
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def LS():
	return sys.stdin.readline().split()

def S():
	return input()

def summarizeList(l):
	sl = sorted(l)
	a = sl[0]
	c = 1
	res = []
	for x in sl[1:]:
		if x == a:
			c += 1
		else:
			res.append([a, c])
			a = x
			c = 1
	res.append([a, c])
	return res

def main():
	s = S()
	n = len(s)
	l = []
	mul = 1
	for x in s[::-1]:
		l.append(mul * int(x) % 2019)
		mul *= 10
		mul %= 2019
	for i in range(n - 1):
		l[i + 1] += l[i]
		l[i + 1] %= 2019
	sl = summarizeList(l)
	ans = 0
	for (x, c) in sl:
		if x == 0:
			ans += c
		if c > 1:
			ans += c * (c - 1) // 2
	return ans
print(main())


s = input()
s = s[::-1]
counts = [0] * 2019
counts[0] = 1
num = 0
d = 1
for char in s:
	num += int(char) * d
	num %= 2019
	d *= 10
	d %= 2019
	counts[num] += 1
ans = 0
for cnt in counts:
	ans += cnt * (cnt - 1) // 2
print(ans)


s = input()
a = [0] * 2019
a[0] += 1
pot = 1
v = 0
ans = 0
for i in range(len(s) - 1, -1, -1):
	digit = int(s[i])
	v = (v + digit * pot) % 2019
	pot = pot * 10 % 2019
	ans += a[v]
	a[v] += 1
print(ans)


S = str(input())
l = len(S)
ans = 0
dig = 1
mod = [0] * 2019
mod[0] = 1
t = 0
for i in range(l):
	t = (t + int(S[-i - 1]) * dig) % 2019
	mod[t] += 1
	dig = dig * 10 % 2019
for j in mod:
	ans = ans + j * (j - 1) // 2
print(ans)


s = input()
n = len(s)
t = [0] * 2019
t[0] = 1
d = 1
tkk = 0
for k in reversed(range(n)):
	tk = tkk + int(s[k]) * d
	tk = tk % 2019
	t[tk] = t[tk] + 1
	tkk = tk
	d = d * 10
	d = d % 2019
ans = 0
for i in t:
	ans = ans + i * (i - 1) // 2
print(ans)


def main():
	s = input()
	s_len = len(s)
	mod = 2019
	d = [0] * mod
	d[0] = 1
	rev_num = 0
	t = 1
	for i in reversed(s):
		rev_num += int(i) * t
		rev_num %= mod
		d[rev_num] += 1
		t *= 10
		t %= mod
	print(sum((i * (i - 1) // 2 for i in d)))

def __starting_point():
	main()
__starting_point()


s = input()
a = 0
mods = [0] * 2019
mods[a] += 1
r = 1
for i in s[::-1]:
	a = (a + int(i) * r) % 2019
	r = r * 10 % 2019
	mods[a] += 1
ans = 0
for i in mods:
	ans += i * (i - 1) // 2
print(ans)


from collections import Counter
N = list(input())
M = [0]
S = 0
K = 1
ans = 0
for i in range(len(N)):
	S += int(N[-i - 1]) * K
	S %= 2019
	K *= 10
	K %= 2019
	M.append(S)
P = Counter(M)
for i in range(2020):
	ans += P[i] * (P[i] - 1) // 2
print(ans)


def solve():
	s = input().split()[0]
	cnt = [0] * 2020
	cnt[0] = 1
	m = 0
	t = 1
	for d in map(int, s[-1::-1]):
		m = (m + d * t) % 2019
		t = t * 10 % 2019
		cnt[m] += 1
	return sum([k * (k - 1) // 2 for k in cnt])
print(solve())


s = input()
MOD = 2019
cnt = [0] * MOD
cnt[0] = 1
cum = 0
for (n, x) in enumerate(reversed(s)):
	cum = (cum + int(x) * pow(10, n, MOD)) % MOD
	cnt[cum] += 1
print(sum((v * (v - 1) // 2 for v in cnt)))


S = list(input())
L = [0] * 2019
L[0] = 1
digit = 1
x = 0
for i in S[::-1]:
	x += digit * int(i)
	digit *= 10
	x %= 2019
	digit %= 2019
	L[x] += 1
ans = 0
for i in L:
	ans += i * (i - 1) // 2
print(ans)


S = input()
(p, q) = (0, 1)
dp = {0: 1}
mod = 2019
for i in range(len(S) - 1, -1, -1):
	p = (p + int(S[i]) * q) % mod
	if p not in dp:
		dp[p] = 0
	dp[p] += 1
	q = q * 10 % mod
cnt = 0
for i in dp:
	cnt += dp[i] * (dp[i] - 1) // 2
print(cnt)


s = list(input())
n = len(s)
ans = 0
s.reverse()
x = 1
tot = 0
count = [0] * 2019
for i in range(n):
	count[tot] += 1
	tot += int(s[i]) * x
	tot %= 2019
	ans += count[tot]
	x = x * 10 % 2019
print(ans)


from collections import Counter
s = input()
n = len(s)
MOD = 2019
L = [0]
for i in range(n):
	l = (int(s[n - 1 - i]) * pow(10, i, MOD) + L[i]) % MOD
	L.append(l)
LC = Counter(L)
r = 0
for v in LC.values():
	r += v * (v - 1) // 2
print(r)


S = input()
a = 0
b = [0] * 2019
No = [None] * 2019
for i in S:
	l = No.copy()
	k = int(i)
	for j in range(2019):
		l[(j * 10 + k) % 2019] = b[j]
	l[k] += 1
	a += l[0]
	b = l
print(a)


s = input()
n = len(s)
dp = [1] + [0] * 2019
now = 0
i = 1
for c in reversed(s):
	now = (now + i * int(c)) % 2019
	dp[now] += 1
	i *= 10
	i %= 2019
ans = sum([i * (i - 1) / 2 for i in dp])
print(int(ans))


s = input()
sr = s[::-1]
mod = [0] * 2019
mod[0] += 1
T = 0
d = 1
for s in sr:
	T = T + int(s) * d
	T %= 2019
	mod[T] += 1
	d = d * 10 % 2019
res = [m * (m - 1) // 2 for m in mod]
print(sum(res))


s = input()
remain = [0] * 2020
now = 0
ans = 0
for i in range(len(s) - 1, -1, -1):
	now += int(s[i]) * pow(10, len(s) - i - 1, 2019)
	ans += remain[now % 2019]
	remain[now % 2019] += 1
ans += remain[0]
print(ans)


S = input()
mod = 2019
L = [0] * mod
n = 0
for i in range(len(S) - 1, -1, -1):
	n += int(S[i]) * pow(10, len(S) - i - 1, mod)
	n %= mod
	L[n] += 1
ans = 0
L[0] += 1
for l in L:
	ans += l * (l - 1) // 2
print(ans)


s = input()
b = [0] * 2019
b[0] = 1
now = 0
m = 2019
c = 1
ans = 0
for i in range(len(s) - 1, -1, -1):
	now += int(s[i]) * c
	now = now % m
	c = c * 10
	ans = ans + b[now]
	b[now] = b[now] + 1
	c = c % m
print(ans)


s = input()
len_s = len(s)
current = 0
mod_dict = dict()
mod_dict[0] = 1
for i in range(len_s - 1, -1, -1):
	c = s[i]
	current = (current + pow(10, len_s - i - 1, 2019) * int(c)) % 2019
	if current in mod_dict:
		mod_dict[current] += 1
	else:
		mod_dict[current] = 1
count = 0
for key in mod_dict:
	count += mod_dict[key] * (mod_dict[key] - 1) // 2
print(count)


mod = 2019
cnt = [0 for i in range(2019)]
cnt[0] = 1
x = 0
ten = 1
ans = 0
for s in input()[::-1]:
	x = (x + int(s) * ten) % mod
	ans += cnt[x]
	cnt[x] += 1
	ten *= 10
	ten %= mod
print(ans)


S = input()
N = len(S)
counter = [0] * 2019
counter[0] = 1
T = 0
R = 1
for i in range(N):
	T = (T + R * int(S[N - i - 1])) % 2019
	R = 10 * R % 2019
	counter[T] += 1
ans = 0
for i in range(2019):
	m = counter[i]
	ans += m * (m - 1) // 2
print(ans)


s = input()
mod = 2019
dic = [0] * mod
dic[0] += 1
tmp = 0
d = 1
for i in reversed(range(len(s))):
	tmp += int(s[i]) * d
	tmp %= mod
	d *= 10
	d %= mod
	dic[tmp] += 1
ans = [i * (i - 1) / 2 for i in dic]
print(int(sum(ans)))


S = input()[::-1]
P = [0] * (len(S) + 1)
a = 0
for (i, j) in enumerate(S):
	a = (a + int(j) * pow(10, i, 2019)) % 2019
	P[i] = a
dp = [0] * 2019
for i in P:
	dp[i % 2019] += 1
print(sum([i * (i - 1) // 2 for i in dp]))


def main():
	(n, mods) = (0, [1] + [0] * 2019)
	for (i, j) in enumerate(reversed(input())):
		n = (n + int(j) * pow(10, i, 2019)) % 2019
		mods[n] += 1
	print(sum([i * (i - 1) // 2 for i in mods]))
main()


s = input()[::-1]
count = [0] * 2019
count[0] += 1
sd = 0
d = 1
for c in s:
	sd += int(c) * d
	sd %= 2019
	d *= 10
	d %= 2019
	count[sd] += 1
ans = 0
for cnt in count:
	ans += cnt * (cnt - 1) // 2
print(ans)


S = input()
M = 2019
dp = [0] * M
dp[0] = 1
t = 0
for (i, s) in enumerate(S[::-1]):
	t = (t + int(s) * pow(10, i, M)) % M
	dp[t] += 1
r = 0
for d in dp:
	r += d * (d - 1) // 2
print(r)


MOD = 2019
S = list(input())
S.reverse()
N = len(S)
S = [int(S[i]) for i in range(N)]
MOD = 2019
a = 1
for i in range(N):
	S[i] *= a
	S[i] %= MOD
	a *= 10
	a %= MOD
T = [0 for _ in range(N + 1)]
for i in range(1, N + 1):
	T[i] += S[i - 1] + T[i - 1]
	T[i] %= MOD
C = [0 for i in range(MOD)]
for i in range(N + 1):
	C[T[i]] += 1
ans = 0
for i in range(MOD):
	ans += C[i] * (C[i] - 1) // 2
print(ans)


s = input()[::-1]
n = len(s)
p = 2019
S = [0 for i in range(n + 1)]
ans = [0] * p
x10 = 1
for (j, i) in enumerate(s):
	S[j + 1] = (S[j] + x10 * int(i)) % p
	x10 *= 10
	x10 %= p
	ans[S[j + 1]] += 1
cnt = ans[0]
for a in ans:
	cnt += a * (a - 1) // 2
print(cnt)


S = input()[::-1]
MOD = 2019
r = 0
C = [0 for _ in range(MOD)]
C[0] = 1
for (i, s) in enumerate(S):
	r += int(s) * pow(10, i, MOD)
	r %= MOD
	C[r] += 1
a = 0
for c in C:
	a += c * (c - 1) / 2
print(int(a))


S = input()
cnt = [0] * 2019
cnt[0] = 1
n = 0
t = 1
for i in reversed(S):
	n += int(i) * t
	n %= 2019
	cnt[n] += 1
	t *= 10
	t %= 2019
print(sum((i * (i - 1) // 2 for i in cnt)))


S = reversed(input())
residuelist = [0]
power = 1
residue = 0
for i in S:
	digit = int(i)
	residue = (residue + power * digit) % 2019
	residuelist.append(residue)
	power = power * 10 % 2019
from collections import Counter
val = Counter(residuelist).values()
ans = 0
for j in val:
	ans += j * (j - 1) // 2
print(ans)


S = input()
MOD = 2019
counter = [0] * 2019
counter[0] = 1
t = 1
tmp = 0
for i in reversed(S):
	tmp += int(i) * t
	tmp %= MOD
	t *= 10
	t %= MOD
	counter[tmp] += 1
ans = sum((i * (i - 1) // 2 for i in counter))
print(ans)


(s, l) = (input(), 2019)
(m, a, r) = ([1] + [0] * l, 0, 0)
for (i, e) in enumerate(s[::-1]):
	a += int(e) * pow(10, i, l)
	r += m[a % l]
	m[a % l] += 1
print(r)


s = list(input())
s = [int(i) for i in s]
now = 0
c = [0] * 2019
c[0] = 1
for (n, i) in enumerate(s[::-1]):
	now += i * pow(10, n, 2019)
	c[now % 2019] += 1
ans = 0
for k in range(2019):
	ans += c[k] * (c[k] - 1) // 2
print(ans)


s = input()
n = len(s)
MOD = 2019
T = [1] + [0] * 2018
(d, p) = (0, 1)
for c in reversed(s):
	d = (d + p * int(c)) % MOD
	p = p * 10 % 2019
	T[d] += 1
print(sum((x * (x - 1) // 2 for x in T)))


def main():
	S = input()[::-1]
	counts = [0] * 2019
	counts[0] = 1
	(res, digit) = (0, 1)
	for i in S:
		res += int(i) * digit
		res %= 2019
		digit *= 10
		digit %= 2019
		counts[res] += 1
	ans = 0
	for i in counts:
		ans += i * (i - 1) // 2
	print(ans)

def __starting_point():
	main()
__starting_point()


from collections import Counter
s = input()[::-1]
ans = 0
lst = [0]
num = 0
p = 1
for i in s:
	lst.append((int(i) * p + lst[-1]) % 2019)
	p = p * 10 % 2019
ans = sum((x * (x - 1) // 2 for x in Counter(lst).values()))
print(ans)


s = str(input())
n = len(s)
x = [0] * 2019
x[0] = 1
m = 0
j = 1
for i in range(n):
	m = (m + int(s[-i - 1]) * j) % 2019
	x[m] += 1
	j = j * 10 % 2019
ans = 0
for i in range(2019):
	ans += x[i] * (x[i] - 1) // 2
print(ans)


S = input()
N = len(S)
T = [0]
for i in range(N):
	p = int(S[-1 - i])
	T.append((T[-1] + pow(10, i, 2019) * p) % 2019)
from collections import Counter
ans = 0
U = dict(Counter(T))
for num in U:
	ans += U[num] * (U[num] - 1) // 2
print(ans)


surplus = [0] * 2019
surplus[0] += 1
d = 1
n = 0
for i in reversed(input()):
	n = (n + int(i) * d) % 2019
	d = d * 10 % 2019
	surplus[n] += 1
print(sum([i * (i - 1) // 2 for i in surplus]))


s = input()
s = s[::-1]
t = 0
x = 1
cnt = [0] * 2019
cnt[0] = 1
for i in s:
	t += int(i) * x
	t %= 2019
	x *= 10
	x %= 2019
	cnt[t] += 1
ans = 0
for i in cnt:
	ans += i * (i - 1) // 2
print(ans)


S = list(map(int, list(input())))
N = len(S)
m = [0] * 2019
m[0] = 1
ans = 0
sm = 0
d = 1
for i in range(N):
	sm = (sm + S[N - 1 - i] * d) % 2019
	m[sm] += 1
	d = d * 10 % 2019
for i in m:
	ans += i * (i - 1) // 2
print(ans)


from collections import Counter
S = input()
N = len(S)
l = [0] * (N + 1)
for i in range(N - 1, -1, -1):
	l[i] = (l[i + 1] + pow(10, N - i, 2019) * int(S[i])) % 2019
r = sum((m * (m - 1) // 2 for m in Counter(l).values()))
print(r)


S = input()
p = 2019
h = 0
d = 1
t = 0
c = [0] * p
c[0] = 1
for s in reversed(S):
	m = int(s) * d % p
	h = (h + m) % p
	t += c[h]
	c[h] += 1
	d = d * 10 % p
print(t)


S = input()
ans = 0
r = [0] * 2019
r[0] = 1
t = 0
base = 1
for c in S[::-1]:
	t = (t + base * int(c)) % 2019
	base = base * 10 % 2019
	r[t] += 1
for k in r:
	ans += k * (k - 1) // 2
print(ans)


S = list(map(int, list(input()[::-1])))
N = len(S)
P = 2019
C = [0] * P
B = 1
t = 0
ans = 0
for i in range(N):
	C[t] += 1
	t = (t + S[i] * B) % P
	ans += C[t]
	B = B * 10 % P
print(ans)


s = str(input())
MOD = 2019
m = 0
digit = 1
mods = [1] + [0] * 2018
for a in s[::-1]:
	m = (m + digit * int(a)) % MOD
	mods[m] += 1
	digit = digit * 10 % MOD
ans = 0
for x in mods:
	ans += x * (x - 1) // 2
print(ans)


S = input()
mod = [0]
for (d, c) in enumerate(S[::-1]):
	mod.append((int(c) * pow(10, d, 2019) + mod[-1]) % 2019)
from collections import *
print(sum((v * (v - 1) // 2 for v in Counter(mod).values())))


S = input()[::-1]
mods = [0] * 2019
mods[0] += 1
f = 0
for i in range(len(S)):
	f = (f + pow(10, i, 2019) * int(S[i])) % 2019
	mods[f] += 1
print(sum([i * (i - 1) // 2 for i in mods]))


S = input()
N = len(S)
map_ = [-1] * 2019
map_[0] = 0
ans = 0
now = 0
for i in range(0, N):
	now = (now + int(S[N - i - 1]) * pow(10, i, 2019)) % 2019
	map_[now] += 1
	ans += map_[now]
print(ans)


import collections
S = input()
l = len(S)
(T, d) = (0, 1)
A = [0] * 2019
A[0] = 1
for i in range(l):
	T += int(S[l - i - 1]) * d
	d *= 10
	T %= 2019
	d %= 2019
	A[T] += 1
B = map(lambda x: x * (x - 1) // 2, A)
print(sum(B))


from collections import deque
s = input()[::-1]
l = [0] * 2019
ten = 1
sm = 0
cnt = 0
l[0] = 1
for i in range(len(s)):
	sm += int(s[i]) * ten
	sm %= 2019
	cnt += l[sm]
	l[sm] += 1
	ten = ten * 10 % 2019
print(cnt)


s = input()
n = len(s)
r = list(reversed(s))
x = 1
t = 0
c = [0] * 2019
ans = 0
for i in range(n):
	c[t] += 1
	t += int(r[i]) * x
	t %= 2019
	ans += c[t]
	x = x * 10 % 2019
print(ans)


s = input()[::-1]
l = [0 for i in range(2019)]
l[0] = 1
(a, b) = (0, 1)
ans = 0
for i in s:
	a += int(i) * b
	a %= 2019
	b *= 10
	b %= 2019
	l[a] += 1
for i in l:
	ans += i * (i - 1) // 2
print(ans)


S = input()
s_rev = S[::-1]
r_list = [0] * 2019
r_list[0] = 1
(num, d) = (0, 1)
for i in range(len(S)):
	num += d * int(s_rev[i])
	num %= 2019
	r_list[num] += 1
	d *= 10
	d %= 2019
ans = 0
for i in range(2019):
	ans += r_list[i] * (r_list[i] - 1) // 2
print(ans)


S = list(input())
P = 0
M = 2019
D = [0] * M
D[0] = 1
(X, Y) = (0, 1)
for i in range(len(S)):
	X += Y * int(S[-i - 1])
	X %= M
	P += D[X]
	D[X] += 1
	Y = Y * 10 % M
print(P)


import copy
s = list(input())
s.reverse()
n = len(s)
MOD = 2019
m = [0] * n
msum = [0] * (n + 1)
cnt = [0] * MOD
cnt[0] = 1
t = 1
for i in range(n):
	m[i] = int(s[i]) * t % MOD
	msum[i + 1] = (msum[i] + m[i]) % MOD
	cnt[msum[i + 1]] += 1
	t = t * 10 % MOD
ans = 0
for i in range(MOD):
	ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)


s = input()
s_len = len(s)
n = 2019
sp = [0] * n
sp[0] = 1
p = 1
d = 0
for i in reversed(s):
	d += int(i) * p
	m = d % n
	sp[m] += 1
	p *= 10
	p %= 2019
result = sum((i * (i - 1) // 2 for i in sp))
print(result)


S = input()
mod = 2019
rem = [0] * mod
rem[0] = 1
now = 0
for (k, v) in enumerate(S[::-1]):
	now += int(v) * pow(10, k, mod)
	rem[now % mod] += 1
ans = 0
for i in rem:
	ans += i * (i - 1) // 2
print(ans)


def inN():
	return int(input())

def inL():
	return list(map(int, input().split()))

def inNL(n):
	return [list(map(int, input().split())) for i in range(n)]
s = input()
n = int(s)
l = len(s)
cnt = 0
mod = [0] * 2019
m = 0
for i in range(l):
	m = (int(s[l - 1 - i]) * pow(10, i, 2019) + m) % 2019
	mod[m] += 1
cnt += mod[0]
for i in range(2019):
	if mod[i] > 1:
		cnt += mod[i] * (mod[i] - 1) / 2
print(int(cnt))


s = input()
n = len(s)
l = [0] * 2019
l[0] = 1
k = 0
mod = 2019
r = 1
for i in range(n - 1, -1, -1):
	k += int(s[i]) * r
	k %= mod
	r *= 10
	r %= mod
	l[k] += 1
ans = 0
for i in l:
	ans += i * (i - 1) // 2
print(ans)


s = input()[::-1]
n = len(s)
mod = [0] * 2019
pre = 0
mod[pre] = 1
x = 1
for i in range(n):
	pre += int(s[i]) * x
	pre %= 2019
	mod[pre] += 1
	x *= 10
	x %= 2019
print(sum([m * (m - 1) // 2 for m in mod]))


S = input()
S = list(reversed(S))
m = 2019
cnt = [0 for i in range(m)]
len_S = len(S)
x = 1
tot = 0
ans = 0
for i in range(len(S)):
	cnt[tot] += 1
	tot += (ord(S[i]) - ord('0')) * x
	tot %= m
	ans += cnt[tot]
	x = x * 10 % m
print(ans)


S = input()
mod = 2019
array = []
for i in range(len(S)):
	x = int(S[len(S) - 1 - i]) * pow(10, i, mod) % mod
	array.append(x)
array2 = [0]
y = 0
for i in range(len(S)):
	y = (y + array[i]) % mod
	array2.append(y)
array3 = [0] * 2019
ans = 0
for i in range(len(array2)):
	z = array2[i]
	ans += array3[z]
	array3[z] += 1
print(ans)


P = 2019
S = input()
N = len(S)
ans = 0
rem = [0] * P
mod = 0
ten = 1
rem[mod] = 1
for i in range(N):
	mod = (mod + int(S[N - i - 1]) * ten) % P
	ten = ten * 10 % P
	rem[mod] += 1
for j in rem:
	ans += j * (j - 1) // 2
print(ans)


S = input()
N = len(S)
A = [int(S[i]) for i in range(N)]
A = A[::-1]
MOD = 2019
p10 = [1] * N
for i in range(1, N):
	p10[i] = p10[i - 1] * 10 % MOD
for i in range(N):
	A[i] = A[i] * p10[i] % MOD
cumsum = [A[0]] * N
for i in range(1, N):
	cumsum[i] = (cumsum[i - 1] + A[i]) % MOD
cnt = [0] * MOD
cnt[0] = 1
for i in range(N):
	cnt[cumsum[i]] += 1
ans = 0
for i in range(MOD):
	ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)


from collections import Counter

def main():
	S = input()
	A = list(map(int, S))[::-1]
	mod = []
	ten = 10
	for i in range(len(A)):
		if i == 0:
			mod += (A[i],)
		else:
			mod += ((mod[i - 1] + ten * A[i]) % 2019,)
			ten = ten * 10 % 2019
	mod += (0,)
	C = Counter(mod)
	print(sum([c * (c - 1) // 2 for c in C.values()]))
main()


s = input()
t = s[::-1]
n = len(s)
resid = [0] * 2019
resid[0] = 1
csum = 0
powoften = 1
for i in range(n):
	csum = (csum + int(t[i]) * powoften) % 2019
	powoften = 10 * powoften % 2019
	resid[csum] += 1
ans = 0
for i in range(2019):
	ans += resid[i] * (resid[i] - 1) // 2
print(ans)


from collections import Counter
S = input()
C = Counter()
MOD = 2019
n = 0
for (i, s) in enumerate(S[::-1]):
	s = int(s)
	n += pow(10, i, MOD) * s % MOD
	C[n % MOD] += 1
C[0] += 1
ans = 0
for v in list(C.values()):
	ans += v * (v - 1) // 2
print(ans)


s = input()
l = len(s)
num = 0
count = 0
dic = {0: 1}
for i in range(l - 1, -1, -1):
	num = (num + int(s[i]) * pow(10, l - i - 1, 2019)) % 2019
	if num not in dic:
		dic[num] = 1
	else:
		dic[num] += 1
for ele in list(dic.values()):
	count += ele * (ele - 1) // 2
print(count)


s = list(map(int, input()))
c = 0
cnt = [0] * 2019
cnt[0] += 1
for k in range(len(s) - 1, -1, -1):
	c = (c + s[k] * pow(10, len(s) - 1 - k, 2019)) % 2019
	cnt[c] += 1
print(sum((x * (x - 1) // 2 for x in cnt)))


A = [0] * 2019
s = input()
a = 0
b = 1
for i in range(len(s)):
	b = b % 2019
	a = (a + int(s[len(s) - 1 - i]) * b) % 2019
	b = b * 10
	A[a] += 1
x = A[0]
for j in range(2019):
	x += int(A[j] * (A[j] - 1) / 2)
print(x)


s = list(input())
MOD = 2019
temp = 0
d = 1
m = [0] * MOD
m[0] = 1
for x in reversed(s):
	temp += int(x) * d
	temp %= MOD
	m[temp] += 1
	d = d * 10 % MOD
ans = 0
for x in m:
	ans += x * (x - 1) // 2
print(ans)


S = str(input())[::-1]
N = len(S)
counter = [0] * 2019
counter[0] = 1
ans = 0
(num, d) = (0, 1)
for c in S:
	num += int(c) * d
	num %= 2019
	d *= 10
	d %= 2019
	counter[num] += 1
for i in counter:
	ans += i * (i - 1) // 2
print(ans)


import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda : sys.stdin.readline().strip()
NI = lambda : int(input())
NMI = lambda : map(int, input().split())
NLI = lambda : list(NMI())
SI = lambda : input()

def combinations_count(n, r):
	if n == 1:
		return 0
	else:
		return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def main():
	S = SI()
	ls = []
	len_S = len(S)
	rem = 0
	for s in range(len_S - 1, -1, -1):
		rem = (rem + int(S[s]) * pow(10, len_S - s - 1, 2019)) % 2019
		ls.append(rem)
	import collections
	cls = collections.Counter(ls)
	clsv = list(cls.values())
	ans = 0
	for p in clsv:
		ans += combinations_count(p, 2)
	ans += cls[0]
	print(ans)

def __starting_point():
	main()
__starting_point()


S = input()
T = [0] * 2019
T[0] = 1
t = 0
ans = 0
dig = 1
for i in range(len(S)):
	t = (t + int(S[-i - 1]) * dig) % 2019
	dig = dig * 10 % 2019
	T[t] += 1
for j in T:
	ans += int(j * (j - 1) / 2)
print(ans)


S = input()
mod = 2019
cnt = [0] * 2019
cur = 0
cnt[cur] = 1
d = 1
for s in S[::-1]:
	cur += int(s) * d
	cur %= mod
	cnt[cur] += 1
	d *= 10
	d %= mod
ans = 0
for c in cnt:
	ans += c * (c - 1) // 2
print(ans)


S = input()
s = int(S)
mod = 2019
c = [0] * (len(S) + 1)
d = [0] * 2019
c[0] = 0
d[0] = 1
for i in range(len(S)):
	c[i + 1] = (c[i] + int(S[-i - 1]) * pow(10, i, mod)) % mod
	d[c[i + 1]] += 1
m = 0
for i in range(2019):
	m += d[i] * (d[i] - 1) // 2
print(m)


s = [int(x) for x in reversed(list(input()))]
n = len(s)
x = [0] * 2019
dp = 0
dim = 1
for si in s:
	dp = (dp + si * dim) % 2019
	x[dp] += 1
	dim = dim * 10 % 2019
ans = x[0]
for i in range(2019):
	ans += x[i] * (x[i] - 1) // 2
print(ans)


y = 2019
a = [0] * y
k = 1
r = p = 0
for c in input()[::-1]:
	a[p] += 1
	p -= int(c) * k
	p %= y
	r += a[p]
	k *= 10
	k %= y
print(r)


def MultipleOf2019():
	S = input()
	s = int(S)
	(num, mod, ans) = (len(S), 2019, 0)
	c = [0 for _ in range(num + 1)]
	d = [0 for _ in range(mod)]
	d[0] = 1
	s = int(S)
	for i in range(num):
		c[i + 1] = (c[i] + int(S[-i - 1]) * pow(10, i, mod)) % mod
		d[c[i + 1]] += 1
	for i in range(mod):
		ans += d[i] * (d[i] - 1) // 2
	print(ans)

def __starting_point():
	MultipleOf2019()
__starting_point()


S = input()
N = len(S)
a = 0
t = 1
d = [0] * 2019
d[0] = 1
for i in range(N):
	a += int(S[N - 1 - i]) * t
	a %= 2019
	t *= 10
	t %= 2019
	d[a] += 1
ans = 0
for n in d:
	ans += n * (n - 1) // 2
print(ans)


s = input()
p = 2019
ans = 0
M = [0] * p
M[0] = 1
tmp = 0
for i in range(len(s)):
	tmp += int(s[-i - 1]) * pow(10, i, p)
	tmp %= p
	ans += M[tmp]
	M[tmp] += 1
print(ans)


s = list(map(int, input()))[::-1]
mods = [0] * 2019
mods[0] = 1
v = 0
d = 1
for n in s:
	v = (v + n * d) % 2019
	d = d * 10 % 2019
	mods[v] = mods[v] + 1
print(sum([m * (m - 1) // 2 for m in mods]))


s = input()[::-1]
n = len(s)
a = [0] * 2019
a[0] = 1
x = 1
p = 0
for i in range(n):
	p += x * int(s[i])
	p %= 2019
	a[p] += 1
	x = x * 10 % 2019
ans = 0
for i in range(2019):
	ans += a[i] * (a[i] - 1) // 2
print(ans)


S = list(map(int, list(input())))
pops = 0
digi = 1
cnt = [0] * 2019
cnt[0] = 1
while S:
	s = S.pop()
	pops = (pops + s * digi) % 2019
	digi = 10 * digi % 2019
	cnt[pops] += 1
ans = 0
for i in range(2019):
	ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)


S = input()
(C, m, T) = (2019, 0, [1] + [0] * 2018)
for (i, s) in enumerate(S[::-1]):
	m = (m + int(s) * pow(10, i, C)) % C
	T[m] += 1
print(sum((T[i] * ~-T[i] // 2 for i in range(2019))))


s = input()[::-1]
mod_cnt = [0] * 2019
mod_cnt[0] = 1
t = 0
d = 1
for c in s:
	t += int(c) * d
	t %= 2019
	mod_cnt[t] += 1
	d *= 10
	d %= 2019
print(sum([m * (m - 1) // 2 for m in mod_cnt]))


S = input()
num = 0
r_lst = [0] * 2019
r_lst[0] = 1
cnt = 0
for (i, s) in enumerate(S[::-1]):
	num = (num + pow(10, i, 2019) * int(s)) % 2019
	cnt += r_lst[num]
	r_lst[num] += 1
print(cnt)


m = 2019
l = [0] * m
l[0] = 1
(s, k) = (0, 1)
for c in reversed(input()):
	k = k * 10 % m
	s = (s + int(c) * k) % m
	l[s] += 1
print(sum((v * (v - 1) // 2 for v in l)))


S = list(input())
S = list(map(int, S))[::-1]
mod = [0] * 2019
mod[0] += 1
ans = 0
temp = 0
p = 1
for i in range(len(S)):
	temp += S[i] * p
	p = p * 10 % 2019
	temp %= 2019
	ans += mod[temp]
	mod[temp] += 1
print(ans)


s = input()
n = 0
ans = 0
A = [0] * 2019
A[0] = 1
for i in range(len(s)):
	n = (n + int(s[-1 - i]) * pow(10, i, 2019)) % 2019
	A[n] += 1
for i in A:
	ans += i * (i - 1) // 2
print(ans)


s = input()[::-1]
c = [0] * 2019
c[0] = 1
mod = 0
ten = 1
ans = 0
for i in s:
	mod = (mod + int(i) * ten) % 2019
	ten = ten * 10 % 2019
	c[mod] += 1
for i in c:
	ans += i * (i - 1) // 2
print(ans)


S = str(input())
N = len(S)
b = [0] * 2019
count = 0
b[0] = 1
t = 0
k = 1
if len(S) < 4:
	print(0)
else:
	t = int(S[-1])
	b[t] += 1
	for i in range(1, N):
		k = k * 10 % 2019
		t = (k * int(S[-i - 1]) + t) % 2019
		b[t] += 1
	for i in b:
		count += i * (i - 1) // 2
	print(count)


s = list(input())
l = [0] * 2019
t = 0
ans = 0
for i in range(len(s)):
	t = (t + pow(10, i, 2019) * int(s[-1 - i])) % 2019
	l[t] += 1
for i in l:
	ans += i * (i - 1) // 2
print(ans + l[0])


s = input()
ch = 0
x = 1
rem = [0] * 2019
ans = 0
rem[0] = 1
for c in reversed(s):
	ch = (ch + int(c) * x) % 2019
	x = x * 10 % 2019
	rem[ch] = rem[ch] + 1
print(sum((v * (v - 1) // 2 for v in rem)))


S = input()
m = 2019
dp = [0] * m
dp[0] = 1
(acc, d) = (0, 1)
for s in S[::-1]:
	acc = (acc + d * int(s)) % m
	dp[acc] += 1
	d = d * 10 % m
print(str(sum([n * (n - 1) // 2 for n in dp])))


S = input()
mod = 2019
t = len(S)
l = [0] * (t + 1)
for i in range(t - 1, -1, -1):
	l[i] = (l[i + 1] + int(S[i]) * pow(10, t - i - 1, mod)) % mod
from collections import Counter

def nC2(n):
	return n * (n - 1) // 2
l = list(Counter(l).values())
ans = 0
for i in l:
	ans += nC2(i)
print(ans)


s = input()
n = len(s)
rui = [0]
juu = [1]
for i in range(n + 5):
	juu.append(juu[-1] * 10 % 2019)
for i in range(n):
	rui.append((rui[-1] + int(s[n - 1 - i]) * juu[i]) % 2019)
ama = [0] * 2019
for i in range(len(rui)):
	ama[rui[i]] += 1
ans = 0

def ui(n):
	return max(0, n * (n - 1) // 2)
for i in range(2019):
	ans += ui(ama[i])
print(ans)


s = input()[::-1]
cnt = [0] * 2020
cnt[0] = 1
tens = 1
rem = 0
ans = 0
for c in s:
	rem = (rem + (ord(c) - ord('0')) * tens) % 2019
	ans += cnt[rem]
	cnt[rem] += 1
	tens = tens * 10 % 2019
print(ans)


S = input()
res = [0] * 2019
res[0] = 1
d = 1
a = 0
for c in reversed(S):
	a += int(c) * d
	a %= 2019
	res[a] += 1
	d *= 10
	d %= 2019
ans = 0
for r in res:
	ans += r * (r - 1) // 2
print(ans)


s = input()
s = s[::-1]
n = len(s)
count = [0] * 2019
count[0] = 1
(num, d) = (0, 1)
for i in s:
	num += int(i) * d
	num %= 2019
	d *= 10
	d %= 2019
	count[num] += 1
ans = 0
for i in count:
	ans += i * (i - 1) // 2
print(ans)


S = input()[::-1]
l = [0] * 2019
a = 1
d = 0
for s in S:
	d = d + int(s) * a
	l[d % 2019] += 1
	a *= 10
	a %= 2019
ans = l[0]
for i in l:
	if i >= 2:
		ans += i * (i - 1) // 2
print(ans)


from collections import Counter
s = input()
n = len(s)
digits = [int(c) for c in s[::-1]]
a = [0] * (n + 1)
p = 2019
for (i, digit) in enumerate(digits):
	a[i + 1] = (digit * pow(10, i, p) + a[i]) % p
counter = Counter(a)
ans = 0
for count in counter.values():
	ans += count * (count - 1) // 2
print(ans)


s = input()
(a, b) = (0, [0] * 2019)
b[0] += 1
for i in range(len(s) - 1, -1, -1):
	a = (a + int(s[i]) * pow(10, len(s) - i - 1, 2019)) % 2019
	b[a] += 1
c = 0
for i in b:
	c += i * (i - 1)
print(c // 2)


s = input()[::-1]
p = 2019
ans = [0] * p
(x10, S) = (1, 0)
for i in s:
	S += x10 * int(i)
	S %= p
	x10 *= 10
	x10 %= p
	ans[S] += 1
cnt = ans[0]
for a in ans:
	cnt += a * (a - 1) // 2
print(cnt)


s = input()
n = len(s)
d = [0] * 2019
d[0] = 1
j = 1
ans = 0
now = 0
for i in s[::-1]:
	now = (now + int(i) * j) % 2019
	ans += d[now]
	d[now] += 1
	j *= 10
	j %= 2019
print(ans)


import sys
readline = sys.stdin.readline
S = readline().rstrip()
DIV = 2019
cur = 0
from collections import defaultdict
dic = defaultdict(int)
for i in range(len(S) - 1, -1, -1):
	cur += int(S[i]) % DIV * pow(10, len(S) - 1 - i, DIV) % DIV
	cur %= DIV
	dic[cur] += 1
ans = 0
for (key, val) in dic.items():
	if key == 0:
		ans += val
	ans += val * (val - 1) // 2
print(ans)


R = [0] * 2019
s = input()
res = 0
for d in map(int, s):
	new = [0] * 2019
	for i in range(2019):
		new[(i * 10 + d) % 2019] += R[i]
	new[d] += 1
	res += new[0]
	R = new
print(res)


S = input()
N = len(S)
P = 2019
res = 0
mp = [0] * P
mp[0] = 1
cur = 0
p10 = 1
for c in S[::-1]:
	cur = (cur + int(c) * p10) % P
	res += mp[cur]
	mp[cur] += 1
	p10 *= 10
	p10 %= P
print(res)


S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
	t = int(s) % mod
	r += t * d
	r %= mod
	d = d * 10 % mod
	p[r] += 1
print(sum([i * (i - 1) // 2 for i in p]))


from collections import defaultdict
S = input()
d = defaultdict(int)
d[0] += 1
mod = 0
R = 1
for i in range(len(S)):
	mod = (mod + R * int(S[len(S) - i - 1])) % 2019
	R = R * 10 % 2019
	d[mod] += 1
ans = 0
for i in list(d.values()):
	if i > 1:
		ans += i * (i - 1) / 2
print(int(ans))


S = input()
N = len(S)
a = [0] * (N + 1)
m = 2019
for (i, c) in enumerate(reversed(S)):
	a[i + 1] = (int(c) * pow(10, i, m) + a[i]) % m
from collections import Counter
c = Counter(a)
r = 0
for (k, v) in c.items():
	r += v * (v - 1) // 2
print(r)


S = input().strip()
num = 0
cnt_mod = {0: 1}
mod = 2019
base_pow = 1
for i in range(len(S)):
	digit = int(S[len(S) - 1 - i])
	num += digit * base_pow % mod
	num %= mod
	base_pow = base_pow * 10 % mod
	cnt_mod.setdefault(num, 0)
	cnt_mod[num] += 1
ans = 0
for (r, c) in list(cnt_mod.items()):
	if c >= 2:
		ans += c * (c - 1) // 2
print(ans)


import collections
s = list(input())
a = [0]
s.reverse()
mod = 2019
mod10 = 1
for i in range(len(s)):
	x = int(s[i])
	y = a[-1]
	ans = (x * mod10 + y) % mod
	a.append(ans)
	mod10 = mod10 * 10 % mod
ans1 = 0
c = collections.Counter(a)
d = list(c.values())
for r in d:
	if r >= 2:
		ans1 += r * (r - 1) // 2
print(ans1)


S = input()[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1
current = 0
x = 1
for s in S:
	current = (current + x * int(s)) % 2019
	ans += mods[current % 2019]
	mods[current % 2019] += 1
	x = x * 10 % 2019
print(ans)


ans = 0
S = input()
a = len(S)
k = 0
c = dict()
mod = 2019
s = 1
c[0] = 1
for i in range(a):
	k += s * int(S[a - i - 1])
	k %= mod
	s *= 10
	s %= mod
	if k in c:
		c[k] += 1
	else:
		c[k] = 1
for i in c:
	ans += c[i] * (c[i] - 1) // 2
print(ans)


S = input()
dp = [0] * (len(S) + 1)
cur = int(S[len(S) - 1])
mod_10 = 1
count_num = [0] * 2019
count_num[0] += 1
for i in range(len(S)):
	dp[len(S) - i - 1] = cur
	count_num[cur] += 1
	mod_10 = mod_10 * 10 % 2019
	if i <= len(S) - 2:
		cur = (cur + int(S[len(S) - i - 2]) * mod_10) % 2019
ans = 0
for i in range(2019):
	ans += count_num[i] * (count_num[i] - 1) // 2
print(ans)


S = input()
S = reversed(S)
(x, tot) = (1, 0)
cnt = [0] * 2019
ans = 0
for (i, s) in enumerate(S):
	cnt[tot] += 1
	tot += int(s) * x
	tot %= 2019
	ans += cnt[tot]
	x = x * 10 % 2019
print(ans)


from collections import Counter
S = list(map(int, list(input())))
MOD = 2019
acc_mod = [0]
for (i, s) in enumerate(S[::-1]):
	acc_mod.append((acc_mod[-1] + s * pow(10, i, MOD)) % MOD)
ans = 0
for v in list(Counter(acc_mod).values()):
	ans += v * (v - 1) // 2
print(ans)


from collections import Counter
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 2019
s = readline().decode().rstrip()
s = s[::-1]
n = len(s)
d = [0] * n
d[0] = int(s[0]) % mod
for i in range(1, n):
	d[i] = (d[i - 1] + int(s[i]) * pow(10, i, mod)) % mod
d = [0] + d
c = Counter(d)
ans = 0
for v in c.values():
	ans += v * (v - 1) // 2
print(ans)


from collections import Counter
s = input()
ls = len(s)
t = [0]
j = 1
for i in range(ls):
	u = (int(s[ls - 1 - i]) * j + t[-1]) % 2019
	t.append(u)
	j = j * 10 % 2019
c = Counter(t)
k = list(c.keys())
ans = 0
for i in k:
	ans += c[i] * (c[i] - 1) / 2
print(int(ans))


s = input()
ls = len(s)
m = [0] * 2019
m[0] += 1
cnt = 0
b = 0
for i in range(ls):
	a = (b + pow(10, cnt, 2019) * int(s[ls - i - 1])) % 2019
	m[a] += 1
	b = a
	cnt += 1
ans = 0
for i in m:
	if i <= 1:
		continue
	ans += i * (i - 1) // 2
print(ans)


from itertools import accumulate
S = input()
R = [1]
for _ in range(len(S) - 1):
	R.append(R[-1] * 10 % 2019)
L = [int(s) * r for (s, r) in zip(reversed(S), R)]
Z = list(accumulate(L, func=lambda a, b: (a + b) % 2019))
T = [1] + [0] * 2018
for z in Z:
	T[z] += 1
f = lambda n: n * (n - 1) // 2
print(sum((f(t) for t in T)))


S = input()
MOD = 2019
count = [0] * MOD
r = 0
t = 1
for i in reversed(S):
	r += int(i) * t
	r %= MOD
	t *= 10
	t %= MOD
	count[r] += 1
count[0] += 1
print(int(sum((i * (i - 1) / 2 for i in count))))


from collections import Counter
S = input()
T = [0]
for (i, a) in enumerate(map(int, reversed(S))):
	T.append((a * pow(10, i, 2019) + T[-1]) % 2019)
print(sum((m * (m - 1) // 2 for m in Counter(T).values())))


M = 2019
S = input() + '0'
t = 1
p = 0
mcnt = [0] * 2019
ans = 0
for x in S[::-1]:
	dm = int(x) * t % M
	am = (dm + p) % M
	ans += mcnt[am]
	mcnt[am] += 1
	t = t * 10 % M
	p = am
print(ans)


s = input()
d = [0] * 2019
dp = 0
d[0] += 1
l = len(s)
r = 1
for i in range(l):
	dp += int(s[l - 1 - i]) * r
	dp %= 2019
	r *= 10
	r %= 2019
	d[dp] += 1
res = 0
for a in d:
	res += a * (a - 1) // 2
print(res)


S = input()
unko = [0] * 2019
tmp = 0
num = 1
for s in S[::-1]:
	s = int(s)
	tmp = (tmp + s * num) % 2019
	num = num * 10 % 2019
	unko[tmp] += 1
ans = 0
ans += (unko[0] + 1) * unko[0] / 2
for i in unko[1:]:
	ans += i * (i - 1) / 2
print(int(ans))


import sys
import numpy as np
input = sys.stdin.readline

def ST():
	return input().rstrip()

def I():
	return int(input())

def MI():
	return list(map(int, input().split()))

def LI():
	return list(MI())
S = ST()
cnt = np.zeros(2019)
cnt[0] = 1
res = 0
tmp = 1
for s in S[::-1]:
	res += int(s) * tmp
	res %= 2019
	cnt[res] += 1
	tmp *= 10
	tmp %= 2019
ans = 0
for c in cnt[cnt >= 2]:
	ans += c * (c - 1) // 2
print(int(ans))


S = input()
M = 2019
cnt = [0] * M
cnt[0] = 1
N = 0
ans = 0
for (i, n) in enumerate(map(int, S[::-1])):
	N = (N + n * pow(10, i, M)) % M
	ans += cnt[N]
	cnt[N] += 1
print(ans)


S = input()
n = len(S)
a = [0] * 2019
MOD = 2019
current = 0
a[0] = 1
for i in range(n):
	current = (current + int(S[n - 1 - i]) * pow(10, i, MOD)) % MOD
	a[current] += 1
ans = 0
for i in range(2019):
	ans += a[i] * (a[i] - 1) // 2
print(ans)


s = list(map(int, list(input())))[::-1]
n = len(s)
chk = [0] * 2019
chk[0] = 1
(t, m, ans) = (1, 0, 0)
for i in s:
	m = (m + t * i) % 2019
	ans += chk[m]
	chk[m] += 1
	t = t * 10 % 2019
print(ans)


s = input()
n = len(s)
p = 0
ten = 1
cnt = [0] * 2019
cnt[0] = 1
ans = 0
for i in reversed(s):
	p = (p + int(i) * ten) % 2019
	ans += cnt[p]
	cnt[p] += 1
	ten = ten * 10 % 2019
print(ans)


s = input()[::-1]
p = 0
dp = [0] * 2019
dp[0] = 1
d = 1
for i in s:
	p = (int(i) * d + p) % 2019
	dp[p] += 1
	d *= 10
	d = d % 2019
ans = 0
for i in dp:
	ans += i * (i - 1) // 2
print(ans)


from collections import Counter
S = input()
S = S + '0'
mod = 2019
p = [-1] * len(S)
r = 0
d = 1
for (i, s) in enumerate(S[::-1]):
	t = int(s) % mod
	r += t * d
	r %= mod
	d = d * 10 % mod
	p[i] = r
ans = 0
c = Counter(p)
for (k, n) in c.most_common():
	if n > 1:
		ans += n * (n - 1) // 2
	else:
		break
print(ans)


mod = 2019
s = input()
n = len(s)
w = 0
d = [0] * mod
p = 1
for i in reversed(range(n)):
	w += int(s[i]) * p
	p *= 10
	p %= mod
	w %= mod
	d[w] += 1
d[0] += 1
o = 0
for x in d:
	o += x * (x - 1) // 2
print(o)


S = str(input())
li = [0] * 2019
ans = 0
li[0] = 1
d = 1
s = 0
for i in S[::-1]:
	s += int(i) * d
	s = s % 2019
	li[s] += 1
	d *= 10
	d = d % 2019
for l in li:
	ans += l * (l - 1) // 2
print(ans)


from math import ceil, floor, factorial, gcd, sqrt, log2, cos, sin, tan, acos, asin, atan, degrees, radians, pi, inf
from itertools import accumulate, groupby, permutations, combinations, product, combinations_with_replacement
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from operator import itemgetter
from heapq import heapify, heappop, heappush
from queue import Queue, LifoQueue, PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)

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

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def MAP1():
	return map(lambda x: int(x) - 1, input().split())

def LIST():
	return list(MAP())

def LIST1():
	return list(MAP1())
s = input()

@lru_cache(None)
def F(s, k):
	if k == len(s) - 1:
		return int(s[k])
	ret = F(s, k + 1) + int(s[k]) * pow(10, len(s) - 1 - k, 2019)
	ret %= 2019
	return ret
a = [0] * 2020
for i in range(len(s)):
	a[F(s, i)] += 1
ans = a[0]
for i in range(2020):
	ans += a[i] * (a[i] - 1) // 2
print(ans)


s = input()
mod = 2019
ls = [1] + [0] * 2018
ans = 0
temp = 0
m = 1
for i in range(len(s)):
	temp = (temp + m * int(s[-i - 1])) % mod
	m = m * 10 % mod
	ls[temp] += 1
for i in ls:
	ans += i * (i - 1) // 2
print(ans)


s = input()
c = [0 for i in range(2019)]
c[0] = 1
mod = 2019
x = 0
for (i, j) in enumerate(s[::-1]):
	x = (x + int(j) * pow(10, i, mod)) % mod
	c[x] += 1
ans = 0
for i in range(mod):
	ans += c[i] * (c[i] - 1) // 2
print(ans)


s = input()
l = len(s)
dp = [0] * 2019
dp[0] = 1
r = 0
for i in range(1, l + 1):
	r += int(s[-i]) * pow(10, i - 1, 2019)
	r %= 2019
	dp[r] += 1
print(sum([i * (i - 1) // 2 for i in dp]))


s = input()
s = s[::-1]
a = 1
b = 0
t = [0] * 2019
t[0] = 1
ans = 0
for i in range(len(s)):
	b += int(s[i]) * a
	b %= 2019
	a *= 10
	ans += t[b]
	t[b] += 1
	a %= 2019
print(ans)


s = input()
n = len(s)
a = [0] * 2019
a[0] = 1
k = 0
ans = 0
mod = 1
for i in range(n - 1, -1, -1):
	k = (k + int(s[i]) * mod) % 2019
	mod = mod * 10 % 2019
	a[k] += 1
for i in a:
	ans += i * (i - 1) * 0.5
print(int(ans))


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, bisect
import sys
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7
stdin = sys.stdin
ni = lambda : int(ns())
nf = lambda : float(ns())
na = lambda : list(map(int, stdin.readline().split()))
nb = lambda : list(map(float, stdin.readline().split()))
ns = lambda : stdin.readline().rstrip()
S = ns()
n = len(S)
T = [0] * (n + 1)
d = {0: 1}
for k in range(n - 1, -1, -1):
	tmp = (T[k + 1] + pow(10, n - k - 1, 2019) * int(S[k])) % 2019
	T[k] = tmp
	if tmp not in list(d.keys()):
		d[tmp] = 1
	else:
		d[tmp] += 1
ans = 0
for (k, v) in list(d.items()):
	ans += v * (v - 1) // 2
print(ans)


s = list(map(int, input()))
s.reverse()
t = len(s)
mod = 2019
arr = [0] * (t + 1)
arr[-2] = s[0]
for i in range(1, t):
	arr[t - i - 1] = (arr[t - i] + s[i] * pow(10, i, mod)) % mod
from collections import Counter
arr = Counter(arr)
ans = 0
for i in arr:
	ans += (arr[i] - 1) * arr[i] // 2
print(ans)


s = input()
ans = 0
u = 0
l = [0] * 2019
l[0] = 1
for (i, n) in enumerate(map(int, s)):
	u = (u + n * pow(10, len(s) - i, 2019)) % 2019
	l[u] += 1
for i in l:
	ans += i * (i - 1) // 2
print(ans)


s = input()
l = len(s)
amari = [0] * 2019
amari[0] = 1
d = 0
digi = 1
for c in s[::-1]:
	d = (int(c) * digi + d) % 2019
	amari[d] += 1
	digi = digi * 10 % 2019
ans = 0
for i in amari:
	ans += i * (i - 1) // 2
print(ans)


S = input()
s = S[::-1]
cnt = [0] * 2019
cnt[0] = 1
number = 0
d = 1
for i in s:
	number += int(i) * d
	cnt[number % 2019] += 1
	d *= 10
	d = d % 2019
ans = 0
for i in cnt:
	ans += i * (i - 1) // 2
print(ans)


s = input()
s = s[::-1]
L = [0]
cnt = 1
for i in range(len(s)):
	L.append((L[-1] + int(s[i]) * cnt) % 2019)
	cnt *= 10
	cnt %= 2019
D = dict()
for j in L:
	if j in D:
		D[j] += 1
	else:
		D[j] = 1
ans = 0
for k in D.values():
	ans += k * (k - 1) // 2
print(ans)