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):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time

def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False



yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False



def main():
    s = list(map(int, S()[::-1]))
    N = len(s)
    P = 2019
    cnts = [0] * P
    cnts[0] = 1
    sum_of_digits = 0

    for i in range(N):
        sum_of_digits += s[i] * pow(10, i, P)
        sum_of_digits %= 2019
        cnts[sum_of_digits] += 1

    ans = 0
    for i in range(P):
        ans += cnts[i] * (cnts[i]-1) // 2
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
S = input()
s_len = len(S)
mod_hash = {0: 1}
mod_temp = 1
mod = 0

for i in range(1, s_len + 1):
	mod = (mod + mod_temp * int(S[-i])) % 2019
	if mod in mod_hash:
		mod_hash[mod] += 1
	else:
		mod_hash[mod] = 1
	mod_temp = (mod_temp * 10) % 2019

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

print(ans)

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

Solution (Python):
import math

def comb_count(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)

S = input()[::-1]
ans = 0

mods = [0] * 2019 
mods[0] = 1
current = 0
tmp = 1

for i in range(len(S)):
    current = int(S[i]) * tmp + current
    mod = current % 2019
    mods[mod] += 1
    tmp = tmp * 10 % 2019

for mod in mods:
    if mod > 1:
        ans += comb_count(mod, 2)

print(ans)

Solution (Python):
import math

def comb_count(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)

S = input()[::-1]
ans = 0

mods = [0] * 2019 
mods[0] = 1
current = 0
tmp = 1

for i in range(len(S)):
    current = (int(S[i]) * tmp + current)
    mod = current % 2019
    
    mods[mod] += 1
    tmp = tmp * 10 % 2019

for mod in mods:
    if mod > 1:
        
        ans += comb_count(mod, 2)

print(ans)

Solution (Python):
import math

def comb_count(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)

S = input()[::-1]
ans = 0

mods = [0] * 2019 
mods[0] = 1
current = 0
tmp = 1

for i in range(len(S)):
    current = (int(S[i]) * tmp + current) % 2019
    mod = current % 2019
    
    mods[mod] += 1
    tmp = tmp * 10 % 2019

for mod in mods:
    if mod > 1:
        
        ans += comb_count(mod, 2)

print(ans)

Solution (Python):
import math




S = input()[::-1]
ans = 0

mods = [0] * 2019 
mods[0] = 1
current = 0
tmp = 1

for i in range(len(S)):
    current = (int(S[i]) * tmp + current) % 2019
    mod = current % 2019
    ans += mods[mod]
    mods[mod] += 1
    tmp = tmp * 10 % 2019




print(ans)

Solution (Python):
s = str(input())
now = [0] * 2019
mod = 2019
ans,cnt = 0,1
lis = [int(s[-(1+i)]) for i in range(len(s))]
for num in lis:
    now[0] += 1
    num *= cnt
    num %= mod
    next = [0] * mod
    for i in range(2019-num):
        next[num+i] += now[i]
    for i in range(num):
        next[i] += now[2019-num+i]
    ans += next[0]
    cnt *= 10
    cnt %= mod
    now = next
print(ans)

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

Solution (Python):
import math
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)


S = readChar()

res = [0]*len(S)
res[-1]=int(S[-1])

d = defaultdict(int)

for i in range(2,len(S)+1):
	re = int(S[i*-1])*pow(10,i-1,2019)
	res[i*-1] = (res[i*-1+1]+re)%2019
	


for i in res:
	d[i]+=1

ans = d[0]
for key in d:
	if d[key]>1:
		ans+=comb(d[key],2)

print(ans)

Solution (Python):
import math
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)


S = readChar()

re = [0]*len(S)
res = [0]*len(S)
res[-1]=int(S[-1])

for i in range(2,len(S)+1):
	re = int(S[i*-1])*pow(10,i-1,2019)
	res[i*-1] = (res[i*-1+1]+re)%2019

d = defaultdict(int)
for i in res:
	d[i]+=1

ans = d[0]
for key in d:
	if d[key]>1:
		ans+=comb(d[key],2)

print(ans)

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

if __name__ == '__main__':
    main()

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

Solution (Python):
import sys
from collections import deque
from collections import defaultdict
import math
import copy

sys.setrecursionlimit(20000000)
s = input()
s = s[::-1]
n = len(s)
dp = [0]*(n+1)
k = 1
a = defaultdict(int)
a[0]+=1
for i in range(n):
  dp[i] = (dp[i-1]+int(s[i])*k)%2019
  k*=10
  k%=2019
  a[dp[i]] += 1
ans = 0
for i in a.keys():
  ans += a[i]*(a[i]-1)/2
print(int(ans))

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

"""
    例： S = '31415926535'
        S[3:8] = '15926535' が 2019 で割り切れるかどうか？
     <=> S[3:-1] - S[8:-1] が 2019 で割り切れるかどうか
     <=> S[3:-1] % 2019 == S[8:-1] % 2019 か
    よって、2019で割ったときの異なるあまりをそれぞれカウントすればよい
"""

mod_cnts = [0] * 2019
mod_cnts[0] = 1 
current_cusum, ans = 0, 0

d = 1

for s in S:
    current_cusum += int(s) * d
    current_cusum %= 2019
    d = d * 10 % 2019
    mod_cnts[current_cusum] += 1

    


for cnt in mod_cnts:
    ans += cnt * (cnt - 1) // 2 
 
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
'''
charに一桁ずつ取り出す。そのMOD2019を考え、累積和をとる
しかし、それぞれの数字には10の累乗がかかっているのでそれについては別途dを用意してMOD2019をとる
つまり、numは1桁目のMOD2019、2桁目のMOD2019に1桁目のMOD2019に加える
'''

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

print(ans)

Solution (Python):
S = input()

n = len(S)

medalist = [0] * 2019
medalist[0] = 1
num = 0
mods = 1

for i in range(n):
    fig = int(S[n - i - 1])
    num = (num + fig * mods) % 2019
    medalist[num] = medalist[num] + 1
    mods = (mods * 10) % 2019

result = 0

for i in range(2019):
    m = medalist[i]
    if m != 0:
        result += m * (m - 1) / 2

print(int(result))

Solution (Python):
from collections import Counter
S=input()[::-1]

X=[0]
md=2019

for i,s in enumerate(S):
    X.append((X[-1]+int(s)*pow(10,i,md))%md)

C=Counter(X)
ans=0
for v in C.values():
    ans+=v*(v-1)//2

print(ans)

Solution (Python):
from collections import Counter



S = input()
S = S[::-1] + '0'

mod = 0
mods = [0] * 2019
mods[0] += 1

i_mod = 1

for i in range(len(S)-1):
    
    i_mod %= 2019
    mod = (int(S[i]) * i_mod + mod) % 2019
    
    mods[mod]+=1
    i_mod *= 10



ans = 0









for m in mods:
    if m > 1:
        ans += (m * (m-1)) // 2

print(ans)

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

mod = 2019
dp = [0]*mod
dp[0] = 1

num, d = 0, 1

for c in s:
    num += int(c)*d
    num %= mod
    d *= 10
    d %= mod
    dp[num] += 1

ans = 0
for cnt in dp:
    if cnt == 0:
        continue
    ans += cnt*(cnt-1)//2

print(ans)

Solution (Python):

S = list(str(input()))
N = len(S)

U = []
for i in range(N):
    U.append(int(S[N-i-1]))


DP = [-1]*(N+1)
DP[0] = 0
now = 0
pnow = 1
for i,u in enumerate(U):
    pnow*=10
    pnow%=2019
    now+=int(u)*pnow
    now%=2019
    DP[i+1] = now
    

tyo = [0]*2019
for dp in DP:
    tyo[dp]+=1

ans = 0
for t in tyo:
    ans+=(t*(t-1))//2
    
print(ans)

Solution (Python):
from collections import defaultdict


def resolve():
    s = input()

    cnt = defaultdict(int)
    cnt[0] += 1
    tmp = 0
    for i, c in enumerate(s[::-1]):
        c = int(c)
        tmp = (tmp + c * pow(10, i, 2019)) % 2019
        cnt[tmp] += 1

    ans = sum(c * (c - 1) // 2 for c in cnt.values())
    print(ans)


resolve()

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

Solution (Python):
from collections import Counter
s = input()[::-1]
T = [0]*(len(s)+1)
digit = 1

for i in range(1,len(s)+1):
    T[i] = (T[i-1]+digit*int(s[i-1]))
    T[i] = T[i] % 2019
    digit = digit * 10
    digit = digit % 2019

S = Counter(T)
ans = 0
for i in S.values():
    ans+=(i*(i-1))//2

print(ans)

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

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

Solution (Python):


import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

S = input()
N = len(S)
P = 2019

A = [0] * (N+1)
for i in range(N):
    A[i+1] = (A[i] + int(S[N-1 - i]) * pow(10, i, P)) % P

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

print(ans)

Solution (Python):
s=list(input())[::-1] 
n=len(s)
amari_lis=[0]*2019 
amari_lis[0]=1 

num=0
kurai=1
for keta in s:
    num+=int(keta)*kurai
    num%=2019
    amari_lis[num]+=1
    kurai*=10
    kurai%=2019 

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

print(int(ans))

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

Solution (Python):
import numpy as np
s = input()
y = 2019
dp = np.zeros(y, dtype="int64")
tmp = np.zeros(y, dtype="int64")
k = 1
r = 0
for c in s[::-1]:
    i = int(c)*k%y
    tmp[i:] = dp[:y-i]
    tmp[:i] = dp[y-i:]
    tmp[i] += 1
    dp, tmp = tmp, dp
    r += dp[0]
    k *= 10
    k %= y
print(r)

Solution (Python):
a=input()
num=len(a)
mod_map={0:1}
moji_int=0
Sn=[0]*(num+1)
tens=[1]*(num+1)
for i in range(-1,-num-1,-1):
    tens[-i]=tens[-i-1]*10%2019
    tmp=int(a[i])*(tens[-i-1])%2019
    Sn[-i]=(Sn[-i-1]+tmp%2019)%2019
    mod=Sn[-i]
    if mod not in mod_map:
        mod_map[mod]=1
    else:
        mod_map[mod]+=1

res=0
for i in mod_map.values():
    res+=int(i*(i-1)/2)
print(res)

Solution (Python):
a=input()
num=len(a)
mod_map={0:1}
moji_int=0
Sn=[0]*(num+1)
tens=[1]*(num+1)
for i in range(-1,-num-1,-1):
    tens[-i]=tens[-i-1]*10%2019
    tmp=int(a[i])*(tens[-i-1])
    Sn[-i]=(Sn[-i-1]+tmp%2019)%2019
    mod=Sn[-i]
    if mod not in mod_map:
        mod_map[mod]=1
    else:
        mod_map[mod]+=1

res=0
for i in mod_map.values():
    res+=int(i*(i-1)/2)
print(res)

Solution (Python):
a=input()
num=len(a)
mod_map={0:1}
moji_int=0
Sn=[0]*(num+1)
tens=[1]*(num+1)
for i in range(-1,-num-1,-1):
    tens[-i]=tens[-i-1]*10%2019
    tmp=int(a[i])*(tens[-i-1])
    Sn[-i]=(Sn[-i-1]+tmp)%2019
    mod=Sn[-i]
    if mod not in mod_map:
        mod_map[mod]=1
    else:
        mod_map[mod]+=1

res=0
for i in mod_map.values():
    res+=int(i*(i-1)/2)
print(res)

Solution (Python):

a=list(reversed(input()))
num=len(a)
mod_map={0:1}
moji_int=0
Sn=0
tens=1
for i in a:
    tmp=int(i)*(tens)
    Sn=(Sn+tmp)%2019
    mod=Sn
    tens=tens*10%2019
    if mod not in mod_map:
        mod_map[mod]=1
    else:
        mod_map[mod]+=1


res=0
for i in mod_map.values():
    res+=int(i*(i-1)/2)
print(res)

Solution (Python):
a=reversed(input())

mod_list=[1]+[0]*2019
moji_int=0
Sn=0
tens=1
for i in a:
    tmp=int(i)*(tens)
    Sn=(Sn+tmp)%2019
    mod=Sn
    tens=tens*10%2019
    mod_list[mod]+=1
res=0
for i in mod_list:
    res+=int(i*(i-1)/2)
print(res)

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

    x = 1
    tot = 0
    cnt = [0] * 2019
    ans = 0

    for i in range(len(S)):
        
        
        
        
        
        
        
        

        cnt[tot] += 1
        tot = (tot + (int(S[i]) * x)) % 2019
        ans += cnt[tot]
        x = (x * 10) % 2019
    
    
    
    
    
    
    
    
    
    
    print(ans)


if __name__ == '__main__':
    main()

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

Solution (Python):
from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque

if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')

def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())


a = input().strip()
n = len(a)
dp = [0]*(n+1)
mp  = defaultdict(int)
dp[n-1] = int(a[n-1])
dp[n] = 0
mp[dp[n]]+=1
mp[dp[n-1]]+=1
for i in range(n-2,-1,-1):
    dp[i] = (dp[i+1]+(int(a[i])*pow(10,(n-i-1),2019))%2019)%2019
    mp[dp[i]]+=1
res =0




for i,v in mp.items():
    res+=v*(v-1)//2
print(res)

Solution (Python):
from collections import Counter
s = input()[::-1]
mod = 2019

x = [0]

for i, j in enumerate(s):
    x.append((x[-1] + int(j) * pow(10,i, mod))%mod)

C = Counter(x)
ans = 0

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

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

a = [0]*2019
a[0] = 1
count = 0
val = 1
current = 0
for c in s:
    current = (current + val * int(c)) % 2019
    count += a[current%2019]
    a[current%2019] += 1
    val = val * 10 % 2019

print(count)

Solution (Python):
s = input()
ans = 0
a = [0] * 2019
a[0] = 1
k = 0
mod = 1
for i in range(len(s) - 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))

Solution (Python):


from collections import Counter


S = input()
s_len = len(S)


ans = 0


nums_2019 = [0]*2019
nums_2019[0] = 1
tmp_num = 0
for i in range(s_len-1, -1, -1):
    tmp_num += int(S[i]) * pow(10, s_len-i-1, 2019)
    nums_2019[tmp_num%2019] += 1


for m_c in nums_2019:
    if m_c>=2:
        ans += m_c * (m_c-1) // 2
print(ans)

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]

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()
a = len(S)
mod = 0
ten = 1
L = [0]*2019 
L[0] = 1
for i in range(a-1,-1,-1):
    mod = (int(S[i])*(ten)+mod) %2019
    L[mod] += 1
    ten = (ten*10)%2019
ans = 0
for i in L:
  ans += i*(i-1)//2
print(ans)

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

Solution (Python):
s = input()[::-1]
l = len(s)
c = [0] * 2019
c[0] = 1
ten = 1
mod = 0
ans = 0

for i in range(l):
    mod = (mod + int(s[i]) * ten) % 2019
    ten = ten * 10 % 2019
    c[mod] += 1

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

print(ans)

Solution (Python):
s = input()
l = len(s)
t = [0] * l
t[l - 1] = int(s[l - 1])
m = [0] * 2019
m[0] = 1
m[int(s[l - 1])] = 1
ten = 10
ans = 0

for i in range(l - 1, 0, -1):
    t[i - 1] = (t[i] + int(s[i - 1]) * ten) % 2019
    ten = ten * 10 % 2019
    m[t[i - 1]] += 1

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

print(ans)

Solution (Python):
S = input() [::-1]
ans = 0
mod = 0
ten = 1
count = [0]* 2019
count[0] = 1
for i in range(len(S)):
    mod = (mod + int(S[i]) * ten) % 2019
    ten = ten*10 % 2019
    count[mod] += 1
for c in count:
    ans += c*(c-1)//2
print(ans)

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

Solution (Python):
S = input() [::-1]
ans = 0
mod = 0
ten = 1
count = [0]* 2019
count[0] = 1
for i in range(len(S)):
    mod = (mod + int(S[i]) * ten) % 2019
    ten = ten*10 % 2019
    count[mod] += 1
for c in count:
    ans += c*(c-1)//2
print(ans)

Solution (Python):
s = input()
p = 2019
mods = [0] * p
mods[0] = 1
current = 0
base = 1
cnt = 0

for c in map(int, s[::-1]):
    current = (current + base * int(c)) % p
    base = base * 10 % p
    mods[current] += 1

print(sum(el*(el-1)//2 for el in mods))

Solution (Python):
from collections import deque, defaultdict

S = input()

L = int(S)
S = S[::-1]
cnt = defaultdict(int)

tmp = 0
answer = 0
for i, s in enumerate(S):
    tmp = (tmp + int(s) * pow(10, i, 2019)) % 2019
    
    if tmp % 2019 == 0:
        answer += cnt[0] + 1
    else:
        answer += cnt[tmp % 2019]
    cnt[tmp % 2019] += 1
    

print(answer)

Solution (Python):
from collections import defaultdict
import random

S = input()
n = len(S)

mp = defaultdict(int)
mp[0] += 1
x = 0
y = 1
for i, s in enumerate(reversed(S)):
    x = (x + int(s) * y) % 2019
    y = (y * 10) % 2019
    mp[x] += 1

ans = 0
for m in mp.values():
    ans += m * (m - 1) // 2

print(ans)

Solution (Python):
s = input()[::-1]
counts = [0]*2019
counts[0] = 1
sum = 0
d = 1
for c in s:
  sum += int(c)*d
  remain = sum%2019
  d *= 10
  d %= 2019
  counts[remain] += 1

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

Solution (Python):
import numpy as np



import sys
input = sys.stdin.readline

from numba import njit, i8



@njit
def loof(a,N):
    M = np.zeros(2019,dtype=np.int16)
    M[0] += 1
    T = 0
    r = 1
    T += a[-1] * r
    T %= 2019
    M[T] += 1
    for i in range(N-2,-1,-1):
        r *= 10
        r %= 2019
        T += a[i] * r
        T %= 2019
        M[T] += 1
    return M













def main():
    S = input().rstrip()
    S = list(map(int,list(S)))
    a = np.array(S)

    N = len(a)

    
    M = loof(a,N)

    res = 0

    for m in M:
        res += m * (m-1) // 2

    print(res)


main()

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

Solution (Python):
s = list(input())
mod = 2019
tot = [0]
ans = 0
dp = [0 for _ in range(2020)]
dp[0] = 1
for i in range(len(s)):
    nx = tot[i] + int(s[i])*(pow(10,(len(s)-i),mod))
    nx %= mod
    if dp[nx] != 0:
        ans += dp[nx]
    dp[nx] += 1
    tot.append(nx)
print(ans)

Solution (Python):
def resolve():
    from collections import defaultdict
    s = input()
    n = len(s)
    d = defaultdict(int)
    d[0] += 1
    j = 0
    for i in range(1, n + 1):
        j += int(s[-i]) * pow(10, i - 1, 2019)
        j %= 2019
        d[j] += 1

    def calc(x): return x * (x - 1) // 2
    ans = 0
    for v in d.values():
        ans += calc(v)
    print(ans)


if __name__ == '__main__':
    resolve()

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

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

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

print(int(sum([ans[i] * (ans[i]-1) for i in range(2019)]) / 2) + ans[0])

Solution (Python):

import sys
import collections

def solve(S: int):
    S = list(map(int, list(str(S))))
    count = collections.defaultdict(int)

    count[0] = 1
    tmp = ''
    prev_modulo = 0
    for idx, s in enumerate(S[::-1]):
        prev_modulo = (s * pow(10, idx, 2019) + prev_modulo) % 2019
        count[prev_modulo] += 1

    result = 0
    for k, v in count.items():
        result += v * (v-1) // 2
    print(result)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  
    solve(S)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

def get_modulos():
    modulos = []
    for i in range(224):
        modulos.append(10**i%2019)
    return modulos

def count_substring(s):
    found_remainder = defaultdict(int)
    current_mod = 0
    found_remainder[0] = 1

    output = 0

    modulos = get_modulos()
    for i in range(len(s)-1,-1,-1):
        digit = s[i]
        current_mod =  (int(digit)*modulos[(len(s)-1-i)%224] % 2019 + current_mod) % 2019
        
        output += found_remainder[current_mod]
        found_remainder[current_mod] += 1
    

    return output

s = input()
print(count_substring(s))

Solution (Python):
import numpy as np

s = input()[::-1]
length = len(s)
a = np.zeros(length, dtype=int)
d = np.zeros(length, dtype=int)
ans = np.zeros(2019, dtype=int)
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 = ans[np.nonzero(ans)]

print(int(sum([ans_c[i] * (ans_c[i]-1) for i in range(ans_c.shape[0])]) / 2) + ans[0])

Solution (Python):

S = input()
N = len(S)

cnt = [0] * 2019

cnt[0] = 1

ans = 0
e = 1; cur = 0
for s in reversed(S):
    cur = (cur + int(s) * e) % 2019

    ans += cnt[cur]

    e = (e * 10) % 2019
    cnt[cur] += 1

print(ans)

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

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    S = list(map(int, input().rstrip("\r\n")))
    N = len(S)
    P = 2019
    S.reverse()
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if S[i] % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        tenpow = 1
        for i in range(N):
            S[i] = S[i] * tenpow % P
            tenpow *= 10
            tenpow %= P
            D[i+1] = (S[i] + D[i]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
s = input()
n = len(s)

mod = 2019
cnt = [0] * mod
cnt[0] = 1
digit = 1
now = 0

for i in range(1, n + 1):
    now += int(s[-i]) * digit
    digit *= 10
    digit %= mod
    now %= mod
    cnt[now] += 1

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

print(ans)

Solution (Python):
n = input()

remainder = [0]*2019
remainder[0] += 1
x = 1
rem = 0

for i in range(1, len(n)+1):
	rem = (rem + int(n[-i])*x)%2019
	remainder[rem] += 1
	x *= 10
	x %= 2019
    
res = 0
for e in remainder:
	res += e*(e-1)//2

print(res)

Solution (Python):
s = input()
s_r = s[::-1]
lmod = [0]
cmod = 0
for n,i in enumerate(s_r):
    cmod += int(i)*pow(10,n,2019) % 2019
    cmod = cmod % 2019
    lmod.append(cmod)

from collections import Counter
r = 0
for _,i in Counter(lmod).items():
    r += i*(i-1)/2

print(int(r))

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

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

Solution (Python):
S = input()

n = len(S)
m = 2019

S_ = S[::-1]

x = 1
total = 0
modlis = [0 for i in range(m)]

ans = 0
for i in range(n):
    modlis[total] += 1
    
    
    
    total += int(S_[i])*x
    
    total %= m
    
    ans += modlis[total]
    
    x = x * 10 % m
    

print(ans)

Solution (Python):
s = input()

l = list(s)
n = len(s)

dp = [0] * 2019
dp[0] = 1
x = 0

for i in range(n):
    x = ((int(l.pop()) * pow(10, i, 2019)) + x) % 2019
    dp[x] += 1
answer = 0

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

Solution (Python):
reverse_S = input()[::-1]
n = len(reverse_S)
count = 0
mod = 0
mods = [0] * 2019
mods[0] = 1
x = 1
for s in reverse_S:
    mod = (mod + (int(s) * x)) % 2019
    mods[mod] = mods[mod] + 1
    x = x * 10
    x = x % 2019

for v in mods:
    count = count + v*(v-1)//2

print(count)

Solution (Python):
P = 2019


def main():
    S = [int(s) for s in input()[::-1]]
    N = len(S)
    A = [0]*N
    d = 1
    for i, s in enumerate(S):
        A[i] = (s * d) % P
        d *= 10
        d %= P
    ans = 0
    from collections import Counter
    acc = [0]*(N+1)
    for i in range(N):
        acc[i+1] = acc[i] + A[i]
        acc[i+1] %= P
    c = Counter(acc)
    for v in c.values():
        ans += v*(v-1)//2
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
S = input()[::-1]
n = len(S)
dp = [0]*2019
dp[0] = 1
X = 0
Y = 1
for s in S:
    Z=(int(s)*Y)%2019
    X = (X+Z)%2019
    dp[X] += 1
    Y = (10*Y)%2019
answer = 0
for i in range(2019):
    answer += dp[i]*(dp[i]-1)/2
print(int(answer))

Solution (Python):



S = input()
size = len(S)
L = [0] * 2019  


tmp = int(S[size - 1])  
tmp_r = 1  
L[0] += 1  

L[tmp] += 1


for i in reversed(range(size - 1)):  
    n = int(S[i])  
    
    tmp_r = (tmp_r * 10) % 2019
    r = (n * tmp_r) % 2019  
    
    tmp = (tmp + r) % 2019
    L[tmp] += 1  

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

print(ans)

Solution (Python):
def resolve():
	s = input()
	s = s[::-1]
	t = [0]*2019
	t[0] = 1
	d = 1
	cur = 0
	m = 2019
	for i in range(len(s)):
		cur = (cur + (int(s[i]) * d % m)) % m
		t[cur] += 1
		d *= 10
		d %= m
	ans = 0
	for v in t:
		ans += v*(v-1)//2
	print(ans)
resolve()