Problem:
 Score : 400 points    Problem Statement 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 1 1817181712114      Sample Output 1 3  Three pairs - (1,5) , (5,9) , and (9,13) - satisfy the condition.       Sample Input 2 14282668646      Sample Output 2 2       Sample Input 3 2119      Sample Output 3 0  No pairs satisfy the condition.

Solution (Python):
def main():
    s = list(input())
    s.reverse()
    MOD = 2019
    tot = 0
    ans = 0
    d = [0 for _ in range(MOD)]
    for i in range(len(s)):
        d[tot] += 1
        x = pow(10, i, MOD)
        p = int(s[i]) * x
        p %= MOD
        tot = (tot + p) % MOD
        ans += d[tot]
    return ans


if __name__ == '__main__':
    print(main())

Solution (Python):
s=input()
N=len(s)
kyonen=2019
ans=0


alist=[]
for i in reversed(range(N)):
    alist.append((int(s[i])*pow(10,(N-1-i),kyonen))%kyonen)


ruisekiwa=[0]
for i in range(N):
    ruisekiwa.append((ruisekiwa[-1]+alist[i])%kyonen)


kazoe=[0]*2019
for i in range(N+1):
    kazoe[ruisekiwa[i]]+=1

for i in range(2019):
    if kazoe[i]>=2:
        ans+=int(kazoe[i]*(kazoe[i]-1)/2)

if ruisekiwa[N]==0:
    ans+=1

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    S = input()
    s_list = list(map(int, list(S)))[::-1]
    MOD = 2019

    sum_v = 0
    cnt = [0] * MOD
    cnt[0] = 1
    x = 1
    for s in s_list:
        sum_v += s * x
        sum_v %= MOD
        x *= 10
        x %= MOD
        cnt[sum_v] += 1
    print(sum([c * (c - 1) // 2 for c in cnt if c > 1]))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    S = input()
    s_list = list(map(int, list(S)))[::-1]
    MOD = 2019

    sum_v = 0
    cnt = [0] * MOD
    cnt[0] = 1
    for i, s in enumerate(s_list):
        sum_v += s * pow(10, i, MOD)
        sum_v %= MOD
        cnt[sum_v] += 1
    print(sum([c * (c - 1) // 2 for c in cnt if c > 1]))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    S = input()
    s_list = list(map(int, list(S)))[::-1]
    MOD = 2019

    sum_v = 0
    cnt = [0] * MOD
    cnt[0] = 1
    for i, s in enumerate(s_list):
        sum_v += s * pow(10, i, MOD)
        sum_v %= MOD
        cnt[sum_v] += 1
    print(sum([c * (c - 1) // 2 for c in cnt if c > 1]))

if __name__ == '__main__':
    main()

Solution (Python):
s = input()[::-1]
sum_of_digits = 0
cnts = [0] * 2019
cnts[0] = 1

d = 1
for c in s:
    sum_of_digits += int(c) * d
    d *= 10
    d %= 2019
    sum_of_digits %= 2019
    cnts[sum_of_digits] += 1

ans = 0
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2

print(ans)

Solution (Python):
mod=2019
s=input()
s=s[::-1]
tmp=0
memo=[0]*2019
memo[0]=1

for i in range(len(s)):
    tmp+=int(s[i])*pow(10,i,mod)
    tmp%=mod
    memo[tmp]+=1

ans=0
for i in memo:
    if i>=2:
        ans+=i*(i-1)//2
print(ans)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
import sys


m = 2019
s = input()
n = len(s)
s = list(map(int, s[::-1]))

x = 1
tot = 0
cnt = [0 for _ in  range(m)]
ans = 0

for i in range(n):
    cnt[tot] += 1
    tot += (s[i] - 0) * x
    tot %= m
    ans += cnt[tot]
    x = x * 10%m

print(ans)

Solution (Python):
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]))

Solution (Python):
s = input()

c = [0 for i in range(2019)]
c[0] = 1
mod = 2019
d = 1
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(2019):
	ans += (c[i]*(c[i]-1))//2
print (ans)

Solution (Python):
S = list(input())
a=[int(x) for x in S] 
a.reverse()

l=[0]*2019
l[0]=1
T=0
d=1

for i in a:
    T+=(int(i)*d)
    T%=2019
    l[T]+=1
    d*=10
    d%=2019
result=0
for n in l:
    result+=n*(n-1)/2
print(int(result))

Solution (Python):
from operator import mul
from functools import reduce
import numpy as np
def ConZ(i):
    z_num = i+int(i*(i-1)/2)
    return z_num

    
    
def cmb(n):
    over = reduce(mul, range(n, n - 2, -1))
    under = reduce(mul, range(1,2 + 1))
    return over // under


S = input()[::-1]
keta = 1
A_num = 0
x = 0
mod = np.array([0]*2019)
for i in range(len(S)):
    A_num += int(S[i:i+1])*keta
    if A_num >= 2019:
        A_num = A_num%2019
    mod[A_num] +=1
    
    keta = keta * 10 % 2019

x += ConZ(mod[0])


for j in range(1,len(mod)):
    x+=cmb(mod[j])
print(x)

Solution (Python):
from operator import mul
from functools import reduce
import numpy as np

    
    

    
    

def cmb(n):
    over = reduce(mul, range(n, n - 2, -1))
    under = reduce(mul, range(1,2 + 1))
    return over // under


S = input()[::-1]
keta = 1
A_num = 0
x = 0
mod = np.array([0]*2019)
mod[0] += 1
for i in range(len(S)):
    A_num += int(S[i:i+1])*keta
    if A_num >= 2019:
        A_num = A_num%2019
    mod[A_num] +=1
    
    keta = keta * 10 % 2019





    

print(int(np.sum(mod* (mod - 1) /2)))

Solution (Python):
from operator import mul
from functools import reduce
import numpy as np

    
    

    
    

def cmb(n):
    over = reduce(mul, range(n, n - 2, -1))
    under = reduce(mul, range(1,2 + 1))
    return over // under


S = input()[::-1]
keta = 1
A_num = 0
x = 0
mod = np.array([0]*2019)
mod[0] += 1
for i in range(len(S)):
    A_num += (int(S[i:i+1])*keta)%2019
    if A_num >= 2019:
        A_num = A_num%2019
    mod[A_num] +=1
    
    keta = keta * 10 % 2019





    

print(int(np.sum(mod* (mod - 1) /2)))

Solution (Python):

s = str(input())

mod = 2019

div_memo = [0 for _ in range(mod)]

num = 0
d = 1
for n in reversed(s):
    num += int(n)*d
    num %= 2019
    div_memo[num] += 1
    d *= 10
    d %= 2019

ans = 0
for i in range(len(div_memo)):
    ans += div_memo[i]*(div_memo[i]-1)//2

ans += div_memo[0]
print(int(ans))

Solution (Python):
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)

Solution (Python):
input = raw_input

M = 2019
s = input()



div = 10

counts = [0] * M


counts[0] += 1
cur = 0

m = 1
for c in reversed(s):
    cur = (int(c) * m + cur) % M
    counts[cur] += 1
    m = (m * 10) % M
    

out = 0
for c in counts:
    out += (c * (c-1) // 2)

print(out)

Solution (Python):
import numpy as np

s = input().strip()
t = 0
counts = np.array([0] * 2019)
counts[0] += 1
m = 1

for a  in reversed(s):
    t = (t + m * int(a)) % 2019
    counts[t] += 1
    m = m * 10 % 2019
    
print(int(np.sum(counts * (counts - 1) /2)))

Solution (Python):
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)

Solution (Python):
A = input()

S = 0
lis = [0] * 2019
lis[0] += 1
l = len(A)+1
d = 1

for n in reversed(A):
    S += int(n)*d
    S %= 2019
    lis[S] += 1
    d *= 10
    d %= 2019

result = 0

for n in lis:
    result += (n*(n-1)//2)


print(result)

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

Solution (Python):
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)

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

Solution (Python):
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)

Solution (Python):
import sys

input = sys.stdin.readline

P = 2019

def main():
    S = input().rstrip()

    n = len(S)
    counts = [0] * P
    counts[0] += 1
    T = 0
    d = 1
    for s in reversed(S):
        T = (T + (d * int(s)) % P) % P
        d = (d * 10) % P
        counts[T] += 1

    ans = 0
    for c in counts:
        ans += c*(c-1)//2  
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
S = input()[::-1]

modCount = [1]+[0]*2018
mod = 0
dig = 1
result = 0

for i in range(len(S)):
  mod = (int(S[i:i+1])*dig+mod)%2019
  dig = (dig*10)%2019
  result += modCount[mod]
  modCount[mod] += 1

print(result)

Solution (Python):
S = input()[::-1]

modCount = [0]*2019
modCount[0] = 1
mod = 0
dig = 1
result = 0

for i in range(len(S)):
  mod = (int(S[i:i+1])*dig+mod)%2019
  dig = (dig*10)%2019
  result += modCount[mod]
  modCount[mod] += 1

print(result)

Solution (Python):
s=raw_input()
str="".join(reversed(s))

dict={}

dict[0]=1

ans=0

sumee=0
ans22=1


for i in str:
	x=sumee+ans22*(ord(i)-ord('0'))
	x=x%2019
	if x in dict:
		ans+=dict[x]
	if x not in dict:
		dict[x]=0
	dict[x]+=1
	sumee=x
	ans22=(ans22*10)%2019

print(ans)

Solution (Python):
str=input()
N=len(str)
a=[0]*N
a[0]=int(str[N-1])
base=10
for i in range(N-1):
    a[i+1]=(int(str[N-i-2])*base+a[i])%2019
    base*=10
    base%=2019
b=[0]*2019
b[0]=1
for i in range(N):
    b[int(a[i])]+=1
ans=0
for i in range(2019):
    if b[i]>1:
        ans+=(b[i]*(b[i]-1))/2
print(int(ans))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
s = str(input())
L = len(s)
dict = [0] * 2019
dict[0] += 1
num = 0
for i in range(L-1, (-1), (-1)):
    num += (int(s[i]) * pow(10,(L-i-1), 2019))%2019
    amari = num % 2019
    dict[amari] += 1
ans = 0
for j in range(2019):
    ans += (dict[j]*(dict[j]-1))/2
print(int(ans))

Solution (Python):


S = input()[::-1] 
N = len(S)


remainder = [0] * 2019
tmp = 0
rad = 1 
for i in range(N):
    r = int(S[i])
    tmp += r*rad
    tmp %= 2019
    
    remainder[tmp] += 1
    rad *= 10
    rad %= 2019

    
    
remainder[0] += 1




answer = 0
for i in range(2019):
    p = remainder[i]
    answer += p*(p-1)/2
print(int(answer))

Solution (Python):
S = input()
size = len(S)
ans = 0
d = [0]*2019
pre = ''
ln = 0
v = 1
  
for i in range(1,size+1):
  md = (ln +(int(S[-1*i])*v))%2019
  d[md] += 1
  ln = md
  v *= 10
  v %= 2019

d[0] += 1
for i in range(2019):
  ans += d[i]*(d[i]-1)/2 

print(int(ans))

Solution (Python):
s = input()
counts = [0]*2019
counts[0] += 1
num = 0
d = 1
for c in reversed(s):
    d %= 2019 
    num += int(c)%2019 * d
    counts[num % 2019] += 1
    d *= 10
ans = 0
for count in counts:
    ans += count*(count -1) // 2
print(ans)

Solution (Python):
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)

Solution (Python):
s=input()
n=len(s)
s=s[::-1]
cnt_mod=[0]
m=0
d=1
for i in range(n):
  m+=int(s[i])*d
  m%=2019
  d*=10
  d%=2019
  cnt_mod.append(m)

from collections import Counter
c=Counter(cnt_mod)
ans=0
for v in c.values():
  ans+=v*(v-1)//2
print(ans)

Solution (Python):
def main():
    s = list(map(int, list(input())))
    r = [0]*len(s)
    r[0] = int(s[-1])
    for i in range(1,len(s)):
        temp = s[-(1+i)]*pow(10,i,2019)
        r[i] = (temp+r[i-1])%2019

    ans = 0
    cts = [0]*2019
    for i in r:
        ans+=cts[i]
        cts[i]+=1
    
    ans+=cts[0]

    print(ans)

main()

Solution (Python):
s = input()
counts = [0]*2019
counts[0] += 1
num = 0
d = 1
for c in reversed(s):
    num += int(c) * d
    counts[num % 2019] += 1
    d *= 10
    d %= 2019
ans = 0
for count in counts:
    ans += count*(count -1) // 2
print(ans)

Solution (Python):
S = input()[::-1]
digits = 1
num, ans = 0, 0
mod_list = [0] * 2019
mod_list[0] = 1

for c in S:
  num += int(c) * digits
  mod_list[num % 2019] += 1
  digits *= 10
  digits %= 2019

for i in range(2019):
  ans += mod_list[i] * (mod_list[i] - 1) // 2
  
print(ans)

Solution (Python):
from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   
    
    len_S = len(S)
    cnt = 0
    for i in range(len_S):
        for j in range(i+3,len_S):
            if j == i+3:
                mod = int(S[len_S-j-1:len_S-i])%3
            else:
                mod = (mod+int(S[len_S-j-1]))%3
            if mod == 0:
                _ = int(S[len_S-j-1:len_S-i])
                if _%673==0:
                    cnt += 1
                    break
    
    print(cnt)


if __name__ == "__main__":
    

    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   
    
    cnt = 0
    mod_arr = [0] * 2019
    mod_arr[0] += 1

    num, dec = 0, 1
    for s in S[::-1]:
        num += int(s)*dec
        num %= 2019
        dec *= 10
        dec %= 2019
        mod_arr[num] += 1

    for i in range(2019):
        if mod_arr[i] > 0:
            cnt += mod_arr[i]*(mod_arr[i]-1)//2
    
    print(cnt)

Solution (Python):
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)

Solution (Python):
p = 2019
s = input()
n = len(s)
M = [0]*(p)
M[0] = 1
m = 0
d = 1

for i in range(n):
  m = (m + int(s[-i-1])*d ) % p  
  M[m] += 1
  d = (d*10) % p
  
ans = 0  
for m in M:
  if m>=2:
    ans += m*(m-1)//2
    
print(ans)

Solution (Python):
s = input()[::-1]
d = 1
num = 0
ans = 0
mod_list = [0] * 2019
mod_list[0] = 1

for char in s:
    num += int(char) * d
    mod_list[num % 2019] += 1
    d *= 10
    d %= 2019

for i in range(2019):
    ans += mod_list[i] * (mod_list[i] - 1) //2

print(ans)

Solution (Python):
s = input()[::-1]
d = 1
num = 0
ans = 0
mod_list = [0] * 2019
mod_list[0] = 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d %= 2019
    mod_list[num % 2019] += 1

for i in range(2019):
    ans += mod_list[i] * (mod_list[i] - 1) //2

print(ans)

Solution (Python):
s = input()[::-1]

n = len(s)
cnt = [0] * 2019
cnt[0] = 1
total = 0
ans = 0
x = 1

for i in range(n):
    total += int(s[i]) * x
    total %= 2019
    x *= 10
    x %= 2019
    ans += cnt[total]
    cnt[total] += 1

print(ans)

Solution (Python):
s = input()
l = len(s)
mod = [1] + [0 for _ in range(2019)]
ml = [0 for _ in range(l + 1)]
ans = 0

tmp = 0
for idx, degit in enumerate(s[::-1]):
    m = int(degit) * pow(10, idx, 2019)
    m = (m + tmp) % 2019
    tmp = m
    ans += mod[m]
    mod[m] += 1

print(ans)

Solution (Python):
s=input()
s=s[::-1]
memo=[0]*2019
memo[0]=1
current=0

for i in range(len(s)):
    current+=int(s[i])*pow(10,i,2019)
    current%=2019
    memo[current]+=1

ans=0
for i in memo:
    if i>=2:
        ans+=i*(i-1)//2
print(ans)

Solution (Python):
S = input()
lmax = len(S)
modulo = list([0]*2019)
mod10 = 10%2019
mod = int(S[-1])%2019
modulo[mod] += 1
for s in reversed(S[:-1]):
    mod = (mod + mod10*int(s))%2019
    modulo[mod] += 1
    mod10 = (mod10*10)%2019
ans = sum(list(map(lambda x: x*(x-1)//2, modulo)))+modulo[0]
print(ans)

Solution (Python):
S = input()

p = 2019
N = len(S)
t = [0]*(N+1)
for i in range(N-1,-1,-1):
  k = (int(S[i]) * pow(10,N-i-1,p))%p
  t[i] = (t[i+1]+k)%p
t= t[:N]
cnt = [0]*p
for i in range(N):
  cnt[t[i]]+=1
ans = 0
for i in range(p):
  m = cnt[i]
  if i == 0 and m > 0:
    ans +=  (m*(m+1))//2
  else:
    ans += (m*(m-1))//2
print(ans)

Solution (Python):
S = input()[::-1]


_MOD = {0: 1}
amari = 0
a = 1
ans = 0

for i in S:
    amari = (amari + int(i) * a) % 2019
    a = (a * 10) % 2019  
    if amari in _MOD:
        _MOD[amari] = _MOD[amari] + 1
    else:
        _MOD[amari] = 1
    
for amari in _MOD:
    m = _MOD[amari]
    ans += (m * (m - 1)) // 2

print(ans)

Solution (Python):
from collections import Counter
s = input()
n = len(s)
mod = [0] * (n+1)

def pow_k(x, n):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x % 2019
        x = x ** 2 % 2019
        n //= 2

    return K * x % 2019

rui = 0
for i in range(n):
    rui = (int(s[n-1-i]) * pow_k(10, i) + rui) % 2019
    mod[n-1-i] = rui
    
b = Counter(mod)
c = list(b.values())
c.sort(reverse = True)

ans = 0
for i in c:
    if i > 1:
        ans += i * (i-1) // 2
    else:
        break

print(ans)

Solution (Python):

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)

Solution (Python):
S=input()
R_S=S[::-1]
ans=0
count=[1]+[0]*2018
remainder=0

i=0
while i<len(S):
    remainder+=int(R_S[i])*pow(10,i,2019)
    remainder=remainder%2019
    ans+=count[remainder]
    count[remainder]+=1
    i+=1

print(ans)

Solution (Python):
s = input()[::-1] 

counts = [0] * 2019
counts[0] = 1

num, d = 0, 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)

Solution (Python):

from sys import stdin, stdout
import math
import bisect
from collections import defaultdict
import datetime
import random

s = stdin.readline().strip()
cnt = 0



    


d = defaultdict(int)
d[0] = 1

now = 0
mul = 1
for each in s[::-1]:
    now = (int(each) * mul + now) % 2019
    cnt += d[now]
    d[now] += 1
    mul = (mul * 10) % 2019
stdout.writelines(str(cnt) + '\n')

Solution (Python):
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 2019


def resolve():
    s = input()
    n = len(s)
    s = s[::-1]

    ruiseki = [0]
    for i in range(n):
        ruiseki.append((ruiseki[-1] + int(s[i]) * pow(10, i, mod)) % mod)

    D = Counter(ruiseki)

    res = 0
    for v in D.values():
        res += v * (v - 1) // 2

    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
s=input()



"""
◆エッセンス1：割り切れるとは、二つに分けた数字のmodが一緒
例)
1817181712114の
18171が2019で割り切れるかどうかを判断する。

18171は(181712114-2114)/10000となるので、
181712114mod2019＝2114mod2019の時、2019で割り切れる。

1817181712114mod2019
 817181712114mod2019
  17181712114mod2019
   7181712114mod2019
    181712114mod2019
     81712114mod2019
      1712114mod2019
       712114mod2019
    　　・・・・
とmodを調べていき、値が同じペアは割り切れる。
"""

"""
◆エッセンス2：大きい数字は都度modを取る

これだけでもループは1回になるんだけど、
|S|が長すぎてTLEとなってしまう（|S|は10**5）
1234567 mod 2019
=(1*10**7)mod2019 + (234567mod2019)
=(1*10mod2019 * 10**6mod2019)+ (234567mod2019)

10**nを毎回modを取ることで、計算する数字の長さを短くする。

"""




cnt=[0]*2019

cnt[0]=1


fac=1
ss=0
for i in range(len(s)):
    
    ss += int(s[len(s)-i-1])*fac
    ss%=2019
    fac=fac*10
    fac%=2019
    cnt[ss]+=1
    

result=0
for c in cnt:
    result+=c*(c-1)//2

print(result)

Solution (Python):
s = input()[::-1]
n = len(s)
x = 1
tot = 0 
cnt = [0 for i in range(2019)] 

ans = 0
for i in range(n):
    
    cnt[tot] += 1
    tot += int(s[i])*x
    
    tot %= 2019
    
    ans += cnt[tot]
    
    x = x*10%2019

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 2019


def resolve():
    s = input()
    n = len(s)
    s = s[::-1]

    ruiseki = 0
    cnt = [0] * mod
    ans = 0
    for i in range(n):
        cnt[ruiseki] += 1
        ruiseki += int(s[i]) * pow(10, i, mod)
        ruiseki %= mod
        ans += cnt[ruiseki]

    print(ans)


if __name__ == '__main__':
    resolve()

Solution (Python):
s = input()

arr = []
amari = [0 for i in range(2019)]
amari[0] +=1
ans = 0
cnt = 0
keta = 1
for i in range(len(s)):
    cnt = (cnt + int(s[-(i+1)]) * keta) % 2019
    arr.append(cnt)
    keta =keta * 10 % 2019

for i in range(len(arr)):
    amari[arr[i]] +=1    
    
for i in amari:
    ans = ans + i * (i-1) // 2
print(ans)

Solution (Python):
from itertools import accumulate
from collections import defaultdict
S = list(input().rstrip())
r = 1
i=len(S)
acc=0
dd = defaultdict(int)
dd[0]+=1
for s in S[::-1]:
    acc+=r*int(s)
    acc%=2019
    r*=10
    r%=2019

    dd[acc]+=1
ans=0
for i in dd.values():
    ans+=(i*(i-1))//2
print(ans)

Solution (Python):
s = input()
s = s[::-1]
l = len(s)
count = [0] * 2019
res = 0
count[res] = 1
d = 1
for i in s:
    res += int(i) * d
    res %= 2019
    count[res] += 1
    d *= 10
    d %= 2019
print(int(sum([m*(m-1)/2 for m in count])))

Solution (Python):
s = input()
s = s[::-1]
n = len(s)

num = [0]*2019
num[0] = 1
number = 0
d = 1

for i in s:
    number += int(i)*d
    num[number%2019] += 1
    d *= 10
    d %= 2019

ans = 0

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

print(ans)

Solution (Python):
s = input()
s = s[::-1]
n = len(s)

num = [0]*2019
num[0] = 1
number = 0
d = 1

for i in s:
    number += int(i)*d
    num[number%2019] += 1
    d *= 10
    d %= 2019

ans = 0

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

print(ans)

Solution (Python):
s = input()
s = s[::-1]
n = len(s)

num = [0]*2019
num[0] = 1
number = 0
d = 1

for i in s:
    number += int(i)*d
    num[number%2019] += 1
    d *= 10
    d %= 2019

ans = 0

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

print(ans)

Solution (Python):
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]))

Solution (Python):
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)

Solution (Python):
s = input()[::-1]
counts = [0] * 2019
counts[0] = 1
num, d = 0, 1
result = 0

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

Solution (Python):
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)

Solution (Python):
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)

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

Solution (Python):
n = input()
countArray = [0] * 2019
count = 0
countArray[0] += 1
nums=0
for i in range(len(n))[::-1]:
    nums = nums + int(n[len(n)-1-i])*pow(10,i,2019)
    countArray[nums%2019]+=1

for i in countArray:
    count += (i * (i - 1)) // 2
print(count)

Solution (Python):
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))

Solution (Python):
from collections import defaultdict

s = input()
n = len(s)
MOD = 2019

dd = defaultdict(int)
dd[0] += 1
prev = 0
for i in reversed(range(n)):
    x = (prev + int(s[i])*pow(10, n-i, MOD)) % MOD
    dd[x] += 1
    prev = x

ans = sum(v*(v-1)//2 for v in dd.values())
print(ans)

Solution (Python):
s = input()

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

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007



def main2():
	
	
	s =  input()
	
	s=[int(c) for c in s]
	ll=len(s)
	ret_count=0
	for i in range(1):
		v = s[i]
		vs=[v]
		for c in s[i+1:]:
			v = (v * 10 + c) % 2019
			vs.append(v)
			if v == 0:
				ret_count += 1
		else:
			pa(vs)	
	print(ret_count)
				
def main():
	
	
	s =  input()
	
	s=[int(c) for c in s]
	s=s[::-1]
	ll=len(s)
	cc=[0]*2019
	p=0
	tt=1
	cc[0]=1
	for i, v in enumerate(s):
		tt *= 10
		tt %= 2019
		p += tt*v
		p %= 2019
		cc[p] += 1
	
	ret = 0
	for v in cc:
		ret += v *(v-1)//2
	print(ret)	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
s = input()


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

Solution (Python):
s = input()


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

Solution (Python):
S = input()

ls =[0 for i in range(2019)]
ls[0] += 1
p_amari = 0
ret = 0
len_s = len(S)
for i in range(len_s) :
	p_amari = ( int(S[len_s-1-i]) * pow(10, i, 2019) + p_amari ) % 2019
	ret += ls[p_amari]
	ls[p_amari] += 1
print(int(ret))

Solution (Python):

line = input()
ln = 0
d = 1
counts=[0]*2019
for i in range(1,len(line) + 1):
    ti1 = (ln +(int(line[-1*i])*d))%2019
    counts[ti1] += 1
    ln = ti1
    d *= 10
    d %= 2019
total = 0
counts[0] +=1
for i in range(len(counts)):
    total += counts[i]*(counts[i] - 1)/2
print(int(total))

Solution (Python):
s = input()
dic = {}
for i in range(2019):
  dic[i] = 0
dic[0] = 1
m = 0
decimal = 1
for j in range(1, len(s)+1):
  m += int(s[-j]) * decimal
  m %= 2019
  dic[m] += 1
  decimal *= 10
  decimal %= 2019

ans = 0
for v in dic.values():
  ans += v*(v-1) // 2
print(ans)

Solution (Python):
s=input()
s_rev=s[::-1]

mod_count=[0]*2019
mod_count[0]=1
d=1
num=0

for char in s_rev:
  num=num+int(char)*d
  num=num%2019
  d=d*10
  d=d%2019
  
  mod_count[num]=mod_count[num]+1

ans=0
for cnt in mod_count:
  ans=ans+cnt*(cnt-1)/2
  
print(int(ans))

Solution (Python):
import sys
from collections import defaultdict

lines = 1
inp = list()

for _ in range(lines):
    inp.append(sys.stdin.readline().strip())


s = inp[0]
n = len(s)

tmp = defaultdict(int)
tmp[0] = 1

b = 0
d = 1

for i in range(1, n + 1):
    a = int(s[n - i])
    b = ((d * a) + b) % 2019
    tmp[b] += 1
    d = (d * 10) % 2019

result = 0

for v in tmp.values():
    result += int(v * (v - 1) / 2)

print(result)

Solution (Python):
S = input()

count = 0
mod_check = [0] * 2019
mod_check[0] = 1
check_S = 0
d = 1
for i in reversed(S):
    check_S += int(i) * d
    check_S %= 2019
    mod_check[check_S] += 1
    d *= 10
    d %= 2019
    count += 1
mod_match = 0
for x in mod_check:
    mod_match += x * (x - 1) // 2
print(mod_match)

Solution (Python):
s = input()
mod = 2019
mod_lst = [0]*mod
mod_lst[0] =1
x = 0
t = 1
for i in reversed(s):
    x += int(i) * t
    y = x % mod
    t *= 10
    t %= mod
    mod_lst[y] += 1


count = 0
for j in mod_lst:
    a = j*(j-1)//2
    count += a
print(count)

Solution (Python):
s = input()
l = len(s)
c = 2019
tm = 1
ti = int(s[-1])
co = [0]*2019
co[ti] += 1
for i in range(1, l):
    tm = tm*10 % c
    ti += int(s[l-i-1]) * tm
    ti = ti % c
    co[ti] += 1
if co[0] != 0:
    co[0] += 1
print(sum([i*(i-1)//2 for i in co]))

Solution (Python):
s = input()[::-1]

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 %= 2019
    cnts[sum_of_digits] += 1

ans = 0

for cnt in cnts:
    ans += cnt * (cnt - 1) // 2
 
print(ans)

Solution (Python):

S = input()[::-1]

counts = [0]*2019

counts[0] = 1

num,d = 0,1
for i in S:
    num += int(i)*d
    num %= 2019
    d *= 10
    
    d %= 2019
    counts[num] += 1

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

print(ans)

Solution (Python):
s = str(input())
cnt = [0]*2019
cnt[0] += 1

si = [0] * (len(s)+1) 
tmp = 0
for i in range(1,len(s)+1): 
    tmp += int(s[-i])%2019 * pow(10,i-1,2019)
    si[i] = tmp % 2019
    cnt[si[i]] += 1

ans = 0
for b in cnt:
    ans += b*(b-1)//2

print(ans)

Solution (Python):
from collections import Counter
s = str(input())

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

c = Counter(si)
ans = 0
for b in list(c.values()):
    ans += b*(b-1)//2

print(ans)

Solution (Python):
s = str(input())
N = len(s)
array = [0]*2019
array[0] += 1
count = 0
d = 1
r = 0
for i in reversed(range(0, N)):
    
    
    r = ( r + int( s[i] ) * d ) % 2019
    d = d * 10 % 2019
    array[r] += 1
for i in array:
    count += i*(i-1)/2
print(int(count))

Solution (Python):
s=input().rstrip()
ans=[0 for i in range(2019)]
tmp=0
a=1
rs=reversed(s)
for i in rs:
    ans[tmp%2019]+=1
    tmp=(tmp+int(i)*a)%2019
    a*=10
    a%=2019
ans[tmp%2019]+=1
count=0
for i in ans:
    count+=int(i*(i-1)/2)
print(count)

Solution (Python):
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]))

Solution (Python):
s = input()[::-1]
counts = [0] * 2019
counts[0] = 1
num, d = 0, 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)

Solution (Python):
s = input()[::-1]

res = 0
cnt = {0: 1}
now = 0
p = 1
for i in range(len(s)):
    now = (now + int(s[i]) * p) % 2019
    res += cnt.get(now, 0)
    p = (p * 10) % 2019
    cnt[now] = cnt.get(now, 0) + 1

print(res)

Solution (Python):
s = input()[::-1]

res = 0
cnt = {0: 1}
now = 0
p = 1
for i in range(len(s)):
    now = (now + (10 * p) * int(s[i])) % 2019
    cnt[now] = cnt.get(now, 0) + 1
    p = (p * 10) % 2019

print(sum(cnt[k] * (cnt[k] - 1) // 2 for k in cnt))

Solution (Python):
s = input()

dp = [0] * 2019
dp2 = [0] * 2019
ans = 0
for i in s:
    i = int(i)

    for j in range(2019):

        dp2[(10*j + i) % 2019] += dp[j]
    dp2[i] += 1
    dp = dp2[:]
    dp2 = [0] * 2019
    
    ans += dp[0]

print(ans)

Solution (Python):
S = str(input())
N = len(S)

ans = 0
amari = [0] * 2019
amari[0] = 1
follow = 0
POW = 1

for i in reversed(S):
  follow += int(i) * POW
  follow %= 2019
  amari[follow] += 1
  POW *= 10
  POW %= 2019
  
print(sum( i * (i-1) // 2 for i in amari ))