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 sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
from numba import njit

@njit('(i4[:],)', cache=True)
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


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

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

@njit('(i4[:],)')
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


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

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):



def solve(*args: str) -> str:
    S = args[0]
    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
    return str(sum([n*(n-1)//2 for n in dp]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):
s = list(input())
p = [0 for i in range(2019)]
n = len(s)
ans = 0
kar = 0
dig = 1
for i in range(n):
    kar = (kar + int(s[n-1-i])*dig)%2019
    dig = (dig*10)%2019
    p[kar] += 1

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

Solution (Python):
import math
s = input()
n = len(s)
count = 0
a = [0 for i in range(2019)]
a[0] = 1
k = 0
b = [0 for i in range(n)]
b[0] = 1
for i in range(1, n):
    b[i] = b[i-1]*10 % 2019


for i in reversed(range(0, n)):
 
    k += (b[n-i-1])*int(s[i]) % 2019
  
    a[k % 2019] += 1

for i in range(len(a)):
    if a[i] >= 2:
        count += (a[i])*(a[i]-1)//2
print(count)

Solution (Python):
S = input()
P = 2019
N = len(S)
num = [0] * P
num[0] = 1
c = 0
ans = 0
dgt = 1
for i in range(N-1, -1, -1):
    c = (c + int(S[i]) * dgt) % P
    dgt *= 10
    dgt %= P
    ans += num[c]
    num[c] += 1

print(ans)

Solution (Python):
import math
s = input()
n = len(s)
count = 0
a = [0 for i in range(2019)]
a[0] = 1
k = 0
b = [0 for i in range(n)]
b[0] = 1
for i in range(1, n):
    b[i] = b[i-1]*10 % 2019


for i in reversed(range(0, n)):
 
    k += (b[n-i-1])*int(s[i]) % 2019
  
    a[k % 2019] += 1

for i in range(len(a)):
    if a[i] >= 2:
        count += (a[i])*(a[i]-1)//2
print(count)

Solution (Python):
S=input()
N=len(S)
R=[0]*(N+1)
mul=1
for i in range(1,N+1):
    R[-(i+1)]=(((int(S[-i])*mul))%(2019)+R[-i])%2019
    mul*=10
    mul%=2019

L=[0]*2019
for r in R:
    L[r]+=1
ans=0
for l in L:
    if l>=2:
        ans+=l*(l-1)//2
print(ans)

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

Solution (Python):
n = input()

MOD = 2019
ans = 0
dp = [0]*MOD
dp[0] = 1
temp = 0

for i in range(len(n)):
    temp = (temp+int(n[-i-1])*int(pow(10, i, MOD))) % MOD
    dp[temp] += 1

for item in dp:
    if item > 1:
        ans += item*(item-1)//2

print(ans)

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

Solution (Python):
import sys
input = sys.stdin.readline

mod = 2019

s = input().rstrip()
n = len(s)

t = [int(s[n - 1])]

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

from collections import Counter

c = Counter(t)
ans = 0

for i in c.keys():
    ans += c[i]*(c[i] - 1) // 2

print(ans)

Solution (Python):
import numpy as np
import collections

def main():
    S = str(input())
    n = len(S)

    T = [-1 for i in range(n+1)]
    T[-1] = 0
    
    
    
    
    b = [1 for i in range(n)]
    for i in reversed(range(n-1)):
        b[i] = b[i+1]*10 % 2019
    

    
    
    

    for i in reversed(range(n)):
        T[i] = (b[i]*int(S[i]) + T[i+1]) % 2019
    


    C = collections.Counter(T)
    
    ans = 0
    for value, count in C.items():
        ans += int(count*(count-1)/2)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def solve():
    s = input()
    n = len(s)
    mod = 2019

    reminder = [0]*mod
    pre_rem = 0

    for i in range(n):
        pre_rem = (int(s[n-i-1])*pow(10, i, mod) + pre_rem) % mod
        reminder[pre_rem] += 1

    ans = reminder[0]
    for rem_num in reminder:
        if rem_num >= 2:
            ans += (rem_num * (rem_num -1))//2
    print(ans)
    
solve()

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

Solution (Python):
S = list(input())
L = [0]*2019
L[0]=1
digit = 1
x = 0

for i in S[::-1]:
    x += digit*int(i)
    digit *= 10
    x %= 2019
    digit %= 2019 
    L[x] += 1

ans = 0

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

print(ans)

Solution (Python):
S = input()
l = len(S)
a = [0]
b = [0]*2019
c = [1]
d = 0
e = 0
for n in range(l-1):
    c.append(c[n]*10%2019)
for n in range(l):
    d += int(S[-n-1])*c[n]
    a.append(d%2019)
for n in range(l+1):
    b[a[n]] += 1
for n in range(2019):
    e += int(b[n]*(b[n]-1)/2)
print(e)

Solution (Python):
S = input()

mod = [0] * 2019
mod[0] = 1
digit = 1
temp = 0
 
for i in S[::-1]:
    temp = (temp + digit * int(i)) % 2019
    mod[temp] += 1
    digit = (digit * 10) % 2019

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

print(ans)

Solution (Python):
s = input()[::-1]
n = len(s)
counts = [0] * 2019
counts[0] = 1
current = 0
d = 1

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

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

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

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):
import collections
S = input()
cnt = 0

mod = [0]
reverse_S = S[::-1]
for i in range(len(reverse_S)):
  now = int(reverse_S[i]) * pow(10,i,2019)
  mod.append((now + mod[i]) % 2019)


c = collections.Counter(mod)
hindo = sorted(c.values(),reverse=True)
for i in hindo:
  if i != 1:
    cnt += i*(i-1)//2


print(cnt)

Solution (Python):
S = input().strip()
p = 2019
t = 1
y = 0
c = [0] * p
c[y] += 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()
N=len(S)
M=2019

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

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

Solution (Python):
import collections
S = input()
cnt = 0

mod = [0]
reverse_S = S[::-1]
for i in range(len(reverse_S)):
  now = int(reverse_S[i]) * pow(10,i,2019)
  mod.append((now + mod[i]) % 2019)


c = collections.Counter(mod)
hindo = c.values()
for i in hindo:
  if i != 1:
    cnt += i*(i-1)//2


print(cnt)

Solution (Python):
def solve(s):
    dp = [0] * 2019
    dp[0] = 1
    r = 0
    for i in range(1, len(s) + 1):
        r += int(s[-i]) * pow(10, i - 1, 2019)
        r %= 2019
        dp[r] += 1
    res = 0
    for r in range(2019):
        res += dp[r] * (dp[r] - 1) // 2
    return res


def main():
    s = input()
    res = solve(s)
    print(res)


def test():
    assert solve("1817181712114") == 3
    assert solve("14282668646") == 2
    assert solve("2119") == 0


if __name__ == "__main__":
    test()
    main()

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

Solution (Python):
import math
s=input()
n=len(s)
count=0
a=[0 for i in range(2019)]
a[0]=1
k=0
b=[0 for i in range(n)]
b[0]=1
for i in range(1,n):
    b[i]=b[i-1]*10%2019
for i in reversed(range(0,n)):
    k+=(b[n-i-1])*int(s[i])%2019
    a[k%2019]+=1        
for i in range(len(a)):
    if a[i]>=2:
        count+=(a[i])*(a[i]-1)//2
print(count)

Solution (Python):


s=input()
p = 2019
ans = 0
l = [0 for i in range(p)]
l[0] = 1
z = 0
ten = 1
tmp = 0
for i in s[::-1]:
    i = int(i)
    tmp=(tmp+i*ten)%p
    ten = (ten*10)%2019
    l[tmp]+=1
for i in l:
    ans+= i*(i-1)//2
print(ans)

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

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

Solution (Python):
S = input()[::-1]
P = [0]*(len(S)+1)
a = 0
for i,j in enumerate((S)):
    a = (a+int(j)*pow(10,i,2019))%2019
    P[i] = a

dp = [0]*2019
for i in P:
    dp[i%2019] += 1
print(sum([i*(i-1)//2 for i in dp]))

Solution (Python):
import numpy
import math


def main():
    S = input()
    Mod = [0 for i in range(2019)]
    Mod[0] = 1
    d = 1
    tmp = 0
    ans = 0
    for c in reversed(S):
        tmp = (d * int(c) + tmp) % 2019
        ans += Mod[tmp]
        
        Mod[tmp] += 1
        d = (d * 10) % 2019

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
S = input()
N = len(S)
table = [1] + [0] * 2020
exp = [1]
for i in range(N):
    exp += [exp[-1]*10 %2019]

curr = 0
for i in range(N):
    curr += int(S[N-1-i])*exp[i]
    curr %= 2019
    table[curr] += 1

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

Solution (Python):
S = input()
N = len(S)
table = [1] + [0] * 2020
exp = [1]
for i in range(N):
    exp += [exp[-1]*10 %2019]

curr = 0
for i in range(N):
    curr += int(S[N-1-i])*exp[i]
    curr %= 2019
    table[curr] += 1

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

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

from collections import defaultdict
amari = defaultdict(lambda:0)
amari[0]=1
num=0
tmp=0

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

from math import factorial

ans = 0
for key,val in amari.items():
    if val>1:
        ans +=val*(val-1)//2

print(ans)

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

mod = 2019

d = {}
d[0] = 1
t, p = 0, 1
for i in range(n-1, -1, -1):
	t = (t + p * int(s[i])) % mod
	d[t] = d.get(t, 0) + 1
	p = p * 10 % mod

print(sum(x * (x - 1) // 2 for x in d.values()))

Solution (Python):
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce


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


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


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


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


def ZIP(n): return zip(*(MAP() for _ in range(n)))


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    S = input()
    N = len(S)

    lis = [0]*2019
    lis[0] = 1

    ct = 0
    for i, x in enumerate(reversed(S)):
        ct += int(x) * pow(10, i, 2019)
        ct %= 2019
        lis[ct] += 1

    ans = 0

    for x in lis:
        if x != 0:
            ans += x*(x-1)//2

    print(ans)


if __name__ == '__main__':
    main()

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

from collections import defaultdict
amari = defaultdict(lambda:0)
amari[0]=1
num=0
tmp=0
ans =0

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

    if amari[tmp]>1:
        val = amari[tmp]
        ans -= (val-1)*(val-2)//2
        ans += (val)*(val-1)//2

print(ans)

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

Solution (Python):
N = input()
a = [0] * 2050
n = 0
p = 1
for i in range(len(N)):
    n += int(N[len(N)-1-i]) * p
    p *= 10
    p %= 2019
    a[int(n) % 2019] += 1
ans = 0
for i in range(2019):
    if i == 0:
        ans += a[i] * (a[i]+1) // 2
    else:
        ans += (a[i]-1) * a[i] // 2
print(ans)

Solution (Python):
def D():
    s = input()
    mods = [0]*2019
    mods[0] = 1
    mod = 0
    for i, element in enumerate(s[::-1]):
        mod += int(element)*pow(10,i,2019)
        mods[mod%2019] += 1
    print(sum(map(lambda x:int(x*(x-1)/2), mods)))
D()

Solution (Python):
def main(): 
    import sys
    from collections import defaultdict
    dic = defaultdict(int)

    input = sys.stdin.readline 

    s = str(input().rstrip())
    m = 0

    for i in range(1, len(s) + 1):
        m_1 = pow(10, i-1,2019)
        m_add = (int(s[-i]) * m_1) % 2019
        m = (m_add + m) % 2019
        dic[m] += 1

    ans1 = 0

    for x in dic.values():
        if x > 1:
            ans1 += x * (x - 1) // 2
    ans2 = dic[0]

    print(ans1 + ans2)

if __name__ == "__main__":
    main()

Solution (Python):




def solve():
    S = input()
    lenS = len(S)
    mod_list = [0] * 2019
    x = 0
    for i in range(lenS):
        x = (int(S[lenS - 1 - i]) * pow(10, i, 2019) + x) % 2019
        mod_list[x] += 1

    result = 0
    for i, ml in enumerate(mod_list):
        if i == 0:
            result += ml
        result += int(ml * (ml - 1) / 2)
    print(result)


if __name__ == '__main__':
    solve()

Solution (Python):
s = list(map(int, list(input())))
s.reverse()
ss = [s[0]]
n = len(s)
mod_digit = 10
for i in range(1, n):
    ss.append((s[i]*mod_digit+ss[i-1])%2019)
    mod_digit = mod_digit*10%2019
keys = [i for i in range(2019)]
counter = {key:0 for key in keys}
for i in range(n):
    counter[ss[i]] += 1
def mC2(m):
    return m*(m-1)//2
ans = 0
for key, item in counter.items():
    ans += mC2(item)
ans += counter[0]
print(ans)

Solution (Python):
S=input()

out=0
l=[0]*2019
x=0
now=1
for i in S[::-1]:
    x+=now*int(i)
    x%=2019
    l[x]+=1

    now*=10
    now%=2019

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

Solution (Python):



def main():
    S = input()
    N = len(S)

    mod_count = [0] * 2019
    mod_count[0] = 1
    ssum = 0
    for i, c in enumerate(S[::-1]):
        ssum = (ssum + int(c) * pow(10, i, 2019)) % 2019
        mod_count[ssum] += 1

    print(sum([m * (m - 1) for m in mod_count]) // 2)


if __name__ == "__main__":
    main()

Solution (Python):




from collections import Counter
s = input()[::-1]
partial = 0
remainders = list()
num = (int(character) for character in s)
for i, int_char in enumerate(num):
  partial = (partial+(int_char*pow(10,i,2019))%2019)%2019
  remainders.append(partial)
histo = Counter(remainders)
non_single_count = int(sum(count*(count-1)/2 for value, count in histo.items() if value!=0))
single_count = int(sum(count+count*(count-1)/2 for value, count in histo.items() if value==0))
print(non_single_count+single_count)

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = sr()
mod_cnt = [0] * 2019
mod_cnt[0] = 1
power = 1
remain = 0
answer = 0
for i in range(len(S)-1, -1, -1):
    remain += int(S[i]) * power
    remain %= 2019
    power *= 10; power %= 2019
    answer += mod_cnt[remain]
    mod_cnt[remain] += 1

print(answer)

Solution (Python):
S = input()
mod_bucket = [0] * 2019
mod_bucket[0] = 1
 
_S = S[::-1]
mod = 0
p = 1
for i in range(len(S)):
    mod = (p * int(_S[i]) + mod) % 2019
    mod_bucket[mod] += 1
    p = p*10%2019

ans = sum([mod*(mod-1)/2 for mod in mod_bucket])
print(int(ans))

Solution (Python):





S = input()
from collections import defaultdict
amari = defaultdict(int)
cur = 0 
keta = 1 
for i in range(len(S)-1,-1,-1):
  cur += int(S[i]) * keta
  cur %= 2019
  keta *= 10
  keta %= 2019
  amari[cur] += 1

ans = 0
if 0 in amari:
  ans += amari[0]
for n in amari.values():
  ans += (n * (n-1)) // 2
  
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(300000)
from collections import Counter

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


S = input()

m = [0]
pow = 1
for i in range(len(S)):
    m.append((m[-1] + int(S[- i - 1]) * pow) % 2019)
    pow = (pow * 10) % 2019


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

Solution (Python):
S = input()

ans = 0
lists = [0 for i in range(2019)]
lists[0] += 1

num = 0
for i in range(len(S) - 1, -1, -1):
    num += pow(10, len(S) - 1 - i, 2019) * int(S[i])
    lists[num % 2019] += 1

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

print(ans)

Solution (Python):
s = input()
ans = 0

U = [0 for i in range(2019)]
mod = 2019
sum_i_to_n = 0
for i in range(len(s)-1, -1, -1):
    
    sum_i_to_n += int(s[i]) * pow(10, len(s)-i-1, mod)
    sum_i_to_n %= mod
    if sum_i_to_n % mod == 0:
        
        ans += 1
    
    
    ans += U[sum_i_to_n]
    U[sum_i_to_n] += 1

print(ans)

Solution (Python):
from collections import defaultdict

S = input()
B = defaultdict(int)
B[0]=1
ans=0
prev=0

for i in range(len(S)):
    m=(prev+int(S[-i-1])*pow(10,i,2019))%2019
    ans+=B[m]
    B[m]+=1
    prev=m

print(int(ans))

Solution (Python):
S = input()

ans = 0
lists = [0 for i in range(2019)]
lists[0] += 1

num = 0
for i in range(len(S) - 1, -1, -1):
    num += pow(10, len(S) - 1 - i, 2019) * int(S[i])
    lists[num % 2019] += 1

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

print(ans)

Solution (Python):
S = input()[::-1]
S_l = len(S)
MOD = 2019
l = [0]*(S_l+1)
ans_l = [0]*2020
l[0] = 0
l[1] = int(S[0]) 
ans_l[0]+=1
ans_l[int(S[0])]+=1

for i in range(2,S_l+1):
  l[i] = (int(S[i-1]) * pow(10,i-1,MOD) + l[i-1])%MOD
  ans_l[l[i]]+=1

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

Solution (Python):
s = input()
ans = 0
mod = [0]*2019
t = s[len(s)-1]
n = 1
for i in range(len(s)-1,-1,-1):

    mod[int(t)%2019] += 1

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

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

l = [0] * 2019
temp = 0
e = 1
for i in range(N-1, -1, -1):
    temp += int(S[i]) * e
    temp %= 2019
    l[temp] += 1
    e *= 10
    e %= 2019

ans = l[0]

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

print(ans)

Solution (Python):
from collections import deque
s = deque(input())
n = len(s)

temp = [0]*2019
t = 1
num = 0
for i in range(n):
    num += int(s.pop())*t 
    temp[num % 2019] += 1
    t = t*10 % 2019 

ans = temp[0]
for t in temp:
    if t > 1:
        ans += t*(t-1)/2

print(int(ans))

Solution (Python):
S = input()
mod_bucket = [0] * 2019
mod_bucket[0] += 1

_S = S[::-1]
mod = 0
p = 1
for i in range(len(S)):
    mod = (p * int(_S[i]) + mod) % 2019
    mod_bucket[mod] += 1
    p *= 10
    p %= 2019

ans = sum([mod*(mod-1)/2 for mod in mod_bucket])
print(int(ans))

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

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

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

Solution (Python):
from sys import stdin



def merge_sort(lst, low, high):
    if low >= high:
        return
    mid = int((low+high)/2)
    merge_sort(lst, low, mid)
    merge_sort(lst, mid+1, high)
    for i in range(low, mid+1):
        tmp_array[i] = lst[i]
    j = high
    for i in range(mid+1, high+1):
        tmp_array[i] = lst[j]
        j -= 1
    i = low
    j = high
    for k in range(low, high+1):
        if tmp_array[i] <= tmp_array[j]:
            lst[k] = tmp_array[i]
            i += 1
        else:
            lst[k] = tmp_array[j]
            j -= 1


S = stdin.readline().rstrip()
N = len(S)
Sp = S

res_map = [0 for _ in range(N)]

aa_list2 = [1]
for i in range(1,N):
    aa_list2.append((aa_list2[i-1]*10)%2019)

tmp_array = [None for _ in range(N)]
res_map[N-1] = int(S[N-1])
index=1
for i in range(N-2,-1,-1):
    res_map[i] = (int(S[i])*aa_list2[index] + res_map[i+1])%2019
    index+=1

res_map.sort()
temp_num=int(res_map[0])
index=1
tot = 0

aa_table = [0 for i in range(2019)]
aa_table2 = [0 for i in range(2019)]
for i in range(len(res_map)):
    aa_table2[res_map[i]]+=1

aa_table2[0]+=1


for i in range(1,N):
    if res_map[i]<res_map[i-1]:
        aa = 2/0

for i in range(1,len(res_map)):
    if temp_num==int(res_map[i]):
        index+=1
        if i==len(res_map)-1:
            aa_table[temp_num]=index
        continue
    else:
        aa_table[temp_num] = index
        index=1
        temp_num=int(res_map[i])
        if i==len(res_map)-1:
            aa_table[temp_num]=1

aa_table[0] += 1 


tot = 0
for i in range(2019):
    tot+=int((aa_table[i]-1)*aa_table[i]/2)








    

print(tot)

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


main()

Solution (Python):
s = input()
mod = 2019
array = [0]*(len(s)+1)

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

    
array.sort()

cnt = 0
w = 1

for i in range(0, len(array)-1):
    if array[i] == array[i+1]:
        w += 1
    else:
        if w >= 2:
            cnt += w*(w-1)/2
            w = 1
            
if w != 1:
    cnt += w*(w-1)/2
    
print(int(cnt))

Solution (Python):
s = input()
mod = 2019
array = [0]*(len(s)+1)

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

    
array.sort()

cnt = 0
w = 1

for i in range(0, len(array)-1):
    if array[i] == array[i+1]:
        w += 1
    else:
        if w >= 2:
            cnt += w*(w-1)/2
            w = 1
            
if w != 1:
    cnt += w*(w-1)/2
    
print(int(cnt))

Solution (Python):
S=input()
mem_mod = [0 for i in range(0,2019,1)]
N = len(S)
counter = 0
S_num_tmp = list(S)
S_num = list(map(int, S_num_tmp))
tmp=10

for i in range(1,N,1):
    S_num[N-i-1] = S_num[N-i] + S_num[N-i-1]*pow(10,i,2019)

for i in range(0,N,1):
    X = S_num[N-i-1] % 2019
    if X==0:
        counter+=1
    counter += mem_mod[X]
    mem_mod[X] += 1
print(counter)

Solution (Python):
import sys
input = sys.stdin.readline

S = input().strip()
l = len(S)
dic = {0:[-1]}
ans = 0
base = 1
mod = 0
for i in range(0, l):
    base = (10 * base) % 2019
    s = base * int(S[l-1-i]) + mod
    mod = s % 2019
    if mod in dic:
        dic[mod].append(i)
    else:
        dic[mod] = [i]

for key, val in dic.items():
    v_len = len(val)
    ans += (v_len * (v_len -1))// 2

print(ans)

Solution (Python):
S = input()
count = 0
exist = [0]*2019
flg = False
N = len(S)
sum = 0
for i, s in enumerate(reversed(S)):
    sum += (int(s) * pow(10, i, 2019)) % 2019
    exist[sum % 2019] += 1
for e in exist:
    if e > 1:
        count += e*(e-1)//2
count += exist[0]
print(count)

Solution (Python):
arr = [0 for i in range(2019)]
arr[0] = 1

s = input()
n = len(s)

num = 0
for i,ele in enumerate(s[::-1]):
    num += int(ele) * pow(10,i,2019)
    arr[num%2019] += 1


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

print(ans)

Solution (Python):
from collections import Counter

S = input()

T = [0]
for i, a in enumerate(map(int, reversed(S))):
    T.append((a * pow(10, i, 2019) + T[-1]) % 2019)

print(sum(m * (m - 1) // 2 for m in Counter(T).values()))

Solution (Python):
from collections import Counter

S = list(input())
T = [int(S[len(S)-1])]
k = int(S[len(S)-1])
for i in range(len(S)-2,-1,-1):
    k = (int(S[i])*pow(10,len(S)-i-1,2019) + k ) % 2019
    T.append(k)

A = Counter(T)
ans = 0
ans += A.get(0,0)
for i in A.values():
    ans += i*(i-1)//2
print(ans)

Solution (Python):
s=input()
n=len(s)
w2019=[1]
i=0
for i in range(i,n):
  w2019.append((w2019[-1]*10)%2019)
v=[int(s[-1])]
for i in range(1,n):
  v.append((v[-1]+int(s[-(i+1)])*w2019[i])%2019)
v.sort()
cnt=0
co=0
if v[0]==0: cnt+=1
for i in range(1,n):
  if v[i]==v[i-1]: co+=1
  elif co!=0:
    cnt+=co*(co+1)//2
    co=0
  if v[i]==0: cnt+=1
cnt+=co*(co+1)//2
print(cnt)

Solution (Python):
from numba import njit
from numpy import int32,zeros,arange
@njit('i4(i4[:])')
def solve(s):
    a=0
    d=zeros(2019,int32)
    for i in s:
        p=zeros(2019,int32)
        for j in range(2019):p[(j*10+i)%2019]+=d[j]
        d=p
        d[i]+=1
        a+=d[0]
    return a
print(solve(int32([*input()])))

Solution (Python):
from collections import defaultdict
s = list(input())[::-1]
n = len(s)
dic = defaultdict(int)
dic[0] = 1
t = 0
for i in range(n):
    t += int(s[i])*pow(10,i,2019) % 2019
    t %= 2019
    dic[t] += 1
ans = 0
for i in dic.keys():
    m = dic[i]
    ans += m*(m-1)//2
print(ans)

Solution (Python):
import collections
S = input()[::-1]
N = len(S)
mod = 2019

ans = 0
x = [0] * N
x[0] = int(S[0]) % mod
ruijo = 10

for i in range(1, N):
    x[i] = (ruijo * int(S[i]) + x[i - 1]) % mod
    if x[i] % mod == 0:
        ans += 1
    ruijo *= 10
    ruijo %= mod
    
d = collections.Counter(x)

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

Solution (Python):
s=[int(i) for i in input()]
s.reverse()

a=0
l=[0 for i in range(2019)]
l[0]=1
b=0.1
for i in range(len(s)):
  b=int(b*10)
  b%=2019
  a+=s[i]*b
  a%=2019
  l[a]+=1

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

Solution (Python):

S = input()

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

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

Solution (Python):
S = input()

n_i_to_j_mod = [0] * (2019+1) 
i_to_end_mod = [0] * (len(S)+1) 

for i in range(1, len(S)+1):
    if i == 1:
        i_to_end_mod[1] = int(S[-1]) % 2019
    else:
        i_to_end_mod[i] = (i_to_end_mod[i-1] + int(S[-i]) * pow(10, i-1, 2019)) % 2019
    n_i_to_j_mod[i_to_end_mod[i]] += 1

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

Solution (Python):

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

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

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

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

Solution (Python):
from sys import stdin



def merge_sort(lst, low, high):
    if low >= high:
        return
    mid = int((low+high)/2)
    merge_sort(lst, low, mid)
    merge_sort(lst, mid+1, high)
    for i in range(low, mid+1):
        tmp_array[i] = lst[i]
    j = high
    for i in range(mid+1, high+1):
        tmp_array[i] = lst[j]
        j -= 1
    i = low
    j = high
    for k in range(low, high+1):
        if tmp_array[i] <= tmp_array[j]:
            lst[k] = tmp_array[i]
            i += 1
        else:
            lst[k] = tmp_array[j]
            j -= 1


S = stdin.readline().rstrip()
N = len(S)
Sp = S

res_map = [0 for _ in range(N)]

aa_list2 = [1]
for i in range(1,N):
    aa_list2.append((aa_list2[i-1]*10)%2019)

tmp_array = [None for _ in range(N)]
res_map[N-1] = int(S[N-1])
index=1
for i in range(N-2,-1,-1):
    res_map[i] = (int(S[i])*aa_list2[index] + res_map[i+1])%2019
    index+=1

res_map.sort()
temp_num=int(res_map[0])
index=1
tot = 0

for i in range(1,N):
    if temp_num==int(res_map[i]):
        index+=1
        continue
    else:
        if temp_num==0:
            tot += int(index*(index+1)/2)
        elif index>1:
            tot += int(index*(index-1)/2)
        index=1
        temp_num=int(res_map[i])


aa_table = [0 for i in range(2019)]
for i in range(len(res_map)):
    aa_table[res_map[i]]+=1

aa_table[0]+=1

tot = 0
for i in range(2019):
    tot+=int((aa_table[i]-1)*aa_table[i]/2)








    

print(tot)

Solution (Python):
S = input()
Smod = [0] * 2019
Smod[0] = 1
ans = 0
S_i = 0
prevmod = 0
k = 1
for i in range(len(S)-1, -1, -1):
  S_i = (int(S[i]) * k + prevmod) % 2019
  ans += Smod[S_i]
  Smod[S_i] += 1
  prevmod = S_i
  k = (k * 10) % 2019
print(ans)

Solution (Python):
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    S = sr()
    N = len(S)
    a = [0]*2019
    a[0] += 1
    t = 0
    r = 1
    for s in reversed(S):
        t += int(s)*r
        t %= 2019
        r *= 10
        r %= 2019
        a[t] += 1
    ans = 0
    for i in range(2019):
        ans += a[i]*(a[i]-1)//2
    print(ans)
resolve()