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):
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)


inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""
from collections import deque, defaultdict, Counter
import math
import sys
sys.setrecursionlimit(10 ** 7)


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



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


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


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


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  


def grid(n): return [s_list() for _ in range(n)]


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




def round_up(a, b):
    """ a/b の切り上げ """
    c = (a + b - 1) / b
    return c


def lcm(a, b):
    """a,bの最小公倍数"""
    return a * b // gcd(a, b)


def main():
    s = input()[::-1]

    cnt = [0] * 2019
    
    cnt[0] = 1
    ans = 0
    b = 0
    t = 1
    for i in s:
        b = b + int(i) * t
        b %= 2019
        cnt[b] += 1
        t *= 10
        t %= 2019

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

S = input()
N = len(S)

dp = [0] * N
dp[N-1] = int(S[N-1])
times = 10
for i in reversed(range(1, N)):
    dp[i-1] = (dp[i] + times * int(S[i-1])) % 2019
    times *= 10
    times %= 2019

T = Counter(dp)
ans = T[0]
for t in T.values():
    ans += t*(t-1)//2

print(ans)

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

Solution (Python):
from collections import Counter

S = input()
MOD = 2019
mods = [0]
r = 0
for i, c in enumerate(S[::-1]):
    r += int(c) * pow(10, i, MOD)
    mods.append(r % MOD)

counter = Counter(mods)


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

print(ans)

Solution (Python):
import collections
S=str(input())

T=[0 for i in range(len(S))]
T[0]=int(S[-1])

for i in range(1,len(S)):
    T[i]=(pow(10,i,2019)*int(S[len(S)-1-i])+T[i-1])%2019
    
cnt=0
T_di=collections.Counter(T)

for key in T_di.keys():
    x=T_di[key]
    cnt+=x*(x-1)/2
    if key==0:
        cnt+=x

print(int(cnt))

Solution (Python):
from collections import defaultdict
S = list(input())[::-1]
n = len(S)
d = defaultdict(int)
d[0] += 1
res = 0
for i, s in enumerate(S):
    res += int(s)*pow(10, i, 2019)
    res %= 2019
    d[res] += 1

ans = 0
for v in d.values():
    ans += v*(v-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):
from collections import defaultdict
S = list(input())[::-1]
n = len(S)
d = defaultdict(int)
d[0] += 1
res = 0
for i, s in enumerate(S):
    res += int(s)*pow(10, i, 2019)
    res %= 2019
    d[res] += 1

ans = 0
for k in d.keys():
    dk = d[k]
    ans += dk*(dk-1)//2
print(ans)

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

Solution (Python):
S = input()
mS, m10, mSd = [0], 1, {}
for i in range(len(S)):
    mS.append((mS[-1] + int(S[-(i + 1)]) * m10) % 2019)
    m10 = (m10 * 10) % 2019
for s in mS[1:]:
    mSd[s] = mSd.get(s, 0) + 1
print(mSd.get(0, 0) + sum([v * (v - 1) // 2 for v in mSd.values()]))

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

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

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

print(ans)

Solution (Python):
mod=2019
s=input()

d={}
temp=1
cnt=0
we=0
d[0]=1
for i in range(len(s)):
  we=(we+int(s[-1-i])*temp)%mod
  temp=temp*10%mod
  
  if we not in d:
    d[we]=1
  else:
    d[we]+=1


for i in d:
  cnt+=(d[i]*(d[i]-1))//2
print(cnt)

Solution (Python):

S = str(input())[::-1]


from collections import Counter

N = len(S)

dp = [0] * (N)
dp[0] = int(S[0])
times =10
for i in range(N-1):
    dp[i+1] = dp[i] + times * int(S[i+1])
    dp[i+1] %= 2019
    times *= 10
    times %= 2019

T = Counter(dp)

answer = T[0]

for t in T.values():
    answer += t*(t-1)//2

print(answer)

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

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]




S = list(map(int, list(input())))

mod = 2019
mod_list = [0]

ten = 1

for num in S[::-1]:
    yo = (num * ten + mod_list[-1]) % mod
    
    mod_list.append(yo)
    
    ten = (ten * 10) % mod

cnt = [0]*2019

for yo in mod_list:
    cnt[yo] += 1

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

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]




S = list(map(int, list(input())))

mod = 2019
mod_list = [0]

ten = 1

for num in S[::-1]:
    yo = (num * ten + mod_list[-1]) % mod
    
    mod_list.append(yo)
    
    ten = (ten * 10) % mod

cnt = [0]*2019

for yo in mod_list:
    cnt[yo] += 1

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

print(ans)

Solution (Python):
s=input()
n=len(s)
s_int=[0]*n
x=(pow(10,n-1))%2019
for i in range(n):
    s_int[i]=(int(s[i])*x)%2019
    x=(x*202)%2019
t=[0]*(n+1)
t[0]=int(s)%2019
for i in range(1,n):
    t[i]=t[i-1]-s_int[i-1]
    t[i]%=2019
t.sort()
t_set=sorted(list(set(t)))
tcnt=[0]*len(t_set)
num=0
for i in range(n+1):
    if t_set[num]==t[i]:
        tcnt[num]+=1
    else:
        num+=1
        tcnt[num]+=1
sum=0
for i in range(len(tcnt)):
    sum+=(tcnt[i]*(tcnt[i]-1))//2
print(sum)

Solution (Python):
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7




S = sys.stdin.buffer.readline().decode().rstrip()
N = len(S)
P = 2019


def solve25():
    ans = 0
    for i, c in enumerate(S):
        if int(c) % P == 0:
            ans += i + 1
    return ans


if P in (2, 5):
    ans = solve25()
    print(ans)
    exit()


U = [0] * N
n = 0
p = 1
for i, c in reversed(list(enumerate(S))):
    n += int(c) * p
    n %= P
    U[i] = n
    p *= 10
    p %= P

counts = [0] * P
for u in U:
    counts[u] += 1

ans = counts[0]
for i in reversed(range(N)):
    
    counts[U[i]] -= 1
    ans += counts[U[i]]
print(ans)

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

li = [0] * n
li[0] = int(s[-1])

for i in range(n-1):
    t = int(s[-i-2])
    li[i+1] = (li[i] + t * pow(10, i+1, 2019)) % 2019

dict1 = {}
for i in li:
    if i in dict1:
        dict1[i] += 1
    else:
        dict1[i] = 1

ans = 0

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

if 0 in dict1:
    ans += dict1[0]

print(ans)

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

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

Solution (Python):
import collections
n = str(input())
ans,m,div = 0,0,[]
for i,j in enumerate(reversed(n)):
    m=(m+int(j)*pow(10,i,2019))%2019
    div.append(m)
div.append(0)
c = collections.Counter(div)
values, counts = zip(*c.most_common())
for i in range(0,len(counts)):
    ans += counts[i] *(counts[i]-1) /2
print(int(ans))

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

Solution (Python):
s=[int(j) for j in input()][::-1]
c=[0]*2019
tmp=0
c[0]+=1
t=1
import numpy as np
for i in s:
    tmp+=t*i
    c[tmp%2019]+=1
    t=t*10%2019
c=np.array(c)
ans=c*(c-1)//2
print(ans.sum())

Solution (Python):

import collections
s = (input())

"""
n = len(s)
ans = 0
for i in range(n-4):
    for j in range(i+4,n+1):
        if int(s[i:j]) % 2019 == 0:
            ans += 1
print(ans)
"""

n = len(s)
ans = 0
l = 0

num = int(s)

tmp = [0 for _ in range(n+1)]

tmp1 = 0

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


c = collections.Counter(tmp)

for i in range(0, 2020):
    a = c[i]
    if a > 0:
        ans += ((a * (a - 1)) // 2)
print(ans)

Solution (Python):
p=d=2019
z=[0]*p
for i,j in enumerate(input()[::-1]):
	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)

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

Solution (Python):
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([int(i*(i-1)/2) for i in mods]))
main()

Solution (Python):
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):
	l=z[i]
	r+=l*(l-1)//2
print(r)

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

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

Solution (Python):
S = str(input())
l = len(S)
mod = [0] * 2019
dp = 0
pw = 1
for i in range(l):
    mod[dp % 2019] += 1
    dp = dp + pw * int(S[-1-i])
    pw = (pw * 10) % 2019
mod[dp % 2019] += 1
cnt = 0
for i in range(2019):
    cnt += (mod[i]*(mod[i]-1))//2
print(cnt)

Solution (Python):
S=str(input())
n=len(S)
mod=2019
ans=0
mod_set=[0]*mod
mod_set[0]+=1
ten=1
k=0
for i in range(n-1,-1,-1):
    k=(k+ten*int(S[i]))%mod
    mod_set[k]+=1
    ten=(ten*10)%mod

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

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

Solution (Python):
p=2019
s,a,d,z=reversed(input()),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)

Solution (Python):
import sys
from collections import Counter
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


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


def main():
    S = input().strip()[::-1]
    MOD = 2019
    T = [0, int(S[0])]
    t10 = 1
    for s in S[1:]:
        t10 *= 10
        t10 %= MOD
        T.append((T[-1] + int(s) * t10) % MOD)

    

    cT = Counter(T)
    
    ans = 0
    for k in T:
        cT[k] -= 1
        ans += cT[k]
    print(ans)


if __name__ == '__main__':
    main()

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

Solution (Python):

s = input()
mods = [0]*2019
mods[0] += 1



base = 1
value = 0
for c in map(int, reversed(s)):
    value += (c*base) % 2019
    base = (base * 10) % 2019
    
    mods[value % 2019] += 1
print(sum([mod*(mod-1)//2 for mod in mods]))

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

Solution (Python):
import math

def readInt():
	return int(input())

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

def readChars():
	return input().split()

s = reversed(input())

ai = 0
si = 0

p = 2019
countarr = [0]*2019

for i, j in enumerate(s):
	ai = (int(j)*pow(10,i,p))%p
	si = (si+ai)%p
	countarr[si]+=1

res = countarr[0]
for i in range(p):
	c = countarr[i]
	res += c*(c-1)//2

print(res)

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

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

Solution (Python):
def main():
  n, mods = 0, [1]+[0]*2019
  d = 1
  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()

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

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

MOD = 2019
mod_cnt = [0]*MOD
mod_cnt[0] = 1
k = 0.1
t = 0
for i in range(1, N+1):
    k = int(k * 10) % MOD
    t = (t + k * int(S[-i])) % MOD
    mod_cnt[t] += 1
ans = 0
for cnt in mod_cnt:
    ans += (cnt * (cnt-1)) // 2
print(ans)

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

Solution (Python):
from collections import defaultdict
s = input()
mod = 2019
dct = defaultdict(int)
dct[0] = 1
x = 0
d = 1
for c in s[::-1]:
    x = (x+int(c)*d)%mod
    d = d*10%mod
    dct[x] += 1
ans = 0
for v in dct.values():ans += v*(v-1)//2
print(ans)

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

Solution (Python):
s = input()
l = len(s)
dp = [0 for i in range(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]))

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

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product
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 debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
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


import random

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

    for i in range(N):
        d = s[i] * pow(10, i, P)
        A[i] = d % P
        if i == 0:
            D[i] = A[i]
        else:
            D[i] = (D[i-1] + A[i]) % P
        
        

    for d in D:
        cnts[d] += 1

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  k=1
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*k)%2019
      k*=10
      k=k%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

if __name__ == '__main__':
  main()

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

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

Solution (Python):
def main():
  import collections
  s = input()
  r = []
  x = 0
  for i in range(len(s)):
    x += int(s[-i-1])*pow(10,i,2019)
    x %= 2019
    r.append(x)
  d = collections.Counter(r) 
  ans = 0
  if 0 in d:
    ans += d[0]
  for k,v in d.items():
    if v >= 2:
      ans += v*(v-1)//2
  print(ans)

main()

Solution (Python):
S = str(input())
h = [int(x) for x in list(S)]
N = len(h)
a = [0] * 2019
a[0] = 1
T = 0
r = 1
c = 0
for i in range(N-1, -1, -1):
    T = (T + h[i] * r) % 2019
    r = r * 10
    r = r % 2019
    c += a[T]
    a[T] += 1
print(c)

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

Solution (Python):
s = list(map(int,input()))
d = [0 for _ in range(2019)]
r = 0
x = 1
for si in reversed(s):
  r += si*x
  r %= 2019
  d[r] += 1
  x *= 10
  x %= 2019
ans = d[0]
for v in d:
  if v >= 2:
    ans += v*(v-1)//2
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np


def solve(S):
    dp = np.zeros(2019, np.int64)
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % 2019
        dp = np.roll(dp, x)
        answer += dp[0]
        pow10 *= 10
        pow10 %= 2019
    return answer


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i4[:],)')(solve)
    cc.compile()


try:
    from my_module import solve
except:
    cc_export()
    exit()

S = np.array(list(read().rstrip()), dtype=np.int32) - ord('0')
print(solve(S))

Solution (Python):
n=0
mods=[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]))

Solution (Python):
S = input()
N = len(S)
mod = 2019
num = [0 for i in range(2019)]
num[0] = 1
t = 1
rem = 0

for i in reversed(S):
    rem += int(i) * t
    rem %= mod
    t *= 10
    t %= mod
    num[rem] += 1

print(int(sum([i * (i-1) / 2 for i in num])))

Solution (Python):
n=0
mods=[0]*2019
mods[0]=1
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]))

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

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

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

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

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

mod = 2019
d = [0 for i in range(2019)]
d[0] = 1
t = 1
rem = 0

for i in reversed(S):
    rem += int(i) * t
    rem %= mod
    t *= 10
    t %= mod
    d[rem] += 1

print(int(sum([i * (i-1) / 2 for i in d])))

Solution (Python):
from collections import defaultdict


s = input()
n = len(s)

dd = defaultdict(int)

d = [0 for i in range(2019)]
d[0] = 1
tmp = 0
_10 = 1

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
















print(sum(v*(v-1)//2 for v in d))

Solution (Python):

import collections
s = (input())

"""
n = len(s)
ans = 0
for i in range(n-4):
    for j in range(i+4,n+1):
        if int(s[i:j]) % 2019 == 0:
            ans += 1
print(ans)
"""

n = len(s)
ans = 0
l = 0

num = int(s)

tmp = [0 for _ in range(n+1)]
ten = [0 for _ in range(n)]
tmp1 = 0
val = 1
for i in range(0,n):
    ten[i] = val
    tmp1 += (int(s[n-i-1]) * val)
    tmp[i+1] = tmp1 % 2019
    val = (val * 10) % 2019


c = collections.Counter(tmp)

for i in range(0, 2020):
    a = c[i]
    if a > 0:
        ans += ((a * (a - 1)) // 2)
print(ans)

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline


def main():
    S = input()
    N = len(S)
    memo = [0] * 2019
    now = 0
    ten = [0] * 200100
    ten[0] = 1
    for j in range(len(ten)-50):
        ten[j+1] = ten[j]*10%2019

    for i in range(N):
        now += int(S[-(i+1)])*ten[i]
        now %= 2019
        memo[now] += 1
    
    ans = 0
    for k in range(2019):
        ans += (memo[k] * (memo[k]-1)) // 2

    ans += memo[0]
    
    
    print(ans)


if __name__ == "__main__":
    main()

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

Solution (Python):
from collections import defaultdict

def main():
    S = input()
    d = defaultdict(int)
    d[0] = 1

    num = 0
    for digit, c in enumerate(S[::-1]):
        num += int(c) * pow(10, digit, 2019)
        num %= 2019
        d[num] += 1
    ans = sum([d[i]*(d[i]-1)//2 for i in range(2019)])
    print(ans)
if __name__ == "__main__":
    main()

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve(S):
    dp = [0] * 2019
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % 2019
        newdp = [0] * 2019
        for i in range(2019-x):
            newdp[x+i] += dp[i]
        for i in range(x):
            newdp[i] += dp[2019-x+i]
        answer += newdp[0]
        pow10 *= 10
        pow10 %= 2019
        dp = newdp
    return answer


S = [x - ord('0') for x in read().rstrip()]
print(solve(S))

Solution (Python):
S = input()
S = list(map(int, S))

r = 0
pow10 = 1
counter = [0] * 2019
counter[0] = 1
for i in range(1, len(S) + 1):
    r = (r + pow10 * S[-i]) % 2019
    counter[r] += 1
    pow10 *= 10
    pow10 %= 2019

ans = 0
for count in counter:
    if count >= 2:
        ans += count * (count - 1) // 2

print(ans)

Solution (Python):
S = input()
N = len(S)
A = [int(S[i]) for i in range(N)]
cnt = [0] * 2019
cnt[0] = 1
p = 1
dp = 0

for i in reversed(range(N)):
    dp = (dp + A[i]*p) % 2019
    cnt[dp] += 1
    p = 10 * p % 2019
ans = 0

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

print(ans)

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

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

Solution (Python):
S = input()
S = list(map(int, S))

r = 0
t = 1
d = [0] * 2019
d[0] = 1
for i in range(1, len(S) + 1):
    r = (r + t * S[-i]) % 2019
    d[r] += 1
    t = t * 10 % 2019

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

print(ans)

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

Solution (Python):
s = list(input())
s.reverse()
r = [0 for _ in range(2019)]
p = 0
for i in range(len(s)):
    p += pow(10, i, 2019) * int(s[i])
    p %= 2019
    r[p] += 1
ans = 0
for i in r:
    if i >= 2:
        ans += ((i - 1) * i) // 2
ans += r[0]
print(ans)

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

res = 0
tmp = [0] * 2019
tmp[0] = 1
sum_of_digits = 0
d = 1

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

for t in tmp:
    res += (t * (t - 1)) // 2

print(res)

Solution (Python):
s = input()
n = 0
ans = 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)

Solution (Python):
S = input()
if len(S) < 4:
  print(0)
else:
  N = len(S)
  x = 0
  d = [0]*2019
  d[0] = 1
  for i, s in enumerate(reversed(S)):
    x = (x+int(s)*pow(10,i,2019))%2019
    d[x] += 1
  print(sum([m*(m-1)//2 for m in d]))

Solution (Python):

import sys


def solve(S: str):

    l = [0] * 2019
    ps = 0
    d = 1
    for i in range(1, len(S) + 1):
        ps += int(S[-i]) * d
        l[ ps % 2019 ] += 1
        d = d * 10 % 2019

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

    return



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

if __name__ == '__main__':
    main()

Solution (Python):
s = input()
n = 0
ans = 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)

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

Solution (Python):
S = input()
mod_list = [0 for i in range(2019)]
mod_list[0] += 1
number = 0
ten_count = 1
for s in S[::-1]:
    number += pow(10, ten_count, 2019) * int(s)
    ten_count += 1
    mod_list[number % 2019] += 1

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

print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np


def solve(S):
    dp = np.zeros(2019, np.int64)
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % 2019
        newdp = np.zeros_like(dp)
        newdp[x:] += dp[:-x]
        newdp[:x] += dp[-x:]
        answer += newdp[0]
        pow10 *= 10
        pow10 %= 2019
        dp = newdp
    return answer


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i4[:],)')(solve)
    cc.compile()


try:
    from my_module import solve
except:
    cc_export()
    exit()

S = np.array(list(read().rstrip()), dtype=np.int32) - ord('0')
print(solve(S))

Solution (Python):
S = input()
S = list(map(int, S))

t = 1
r = 0
d = [0] * 2019
d[0] += 1
for n in reversed(S):
    r = (r + n * t) % 2019
    t = t * 10 % 2019
    d[r] += 1

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

print(ans)

Solution (Python):
import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)
S = input()[::-1]
N = len(S)
cnt = [0]*(N+1)
ans = 0
keta = 1
for i in range(N):
    cnt[i] = (cnt[i-1] + int(S[i])*keta)%2019
    keta *= 10
    keta %= 2019
cnt2 = [0]*2020
for i in cnt:
    cnt2[i] += 1
for i in cnt2:
    if i >= 2:
        ans += C(i,2)
print(ans)