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


def solve(S):
    dp = np.zeros(2019, np.int64)
    temp = np.empty_like(dp)
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % 2019
        temp[x:] = dp[:-x]
        temp[:x] = dp[-x:]
        dp, temp = temp, dp
        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):
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.empty_like(dp)
        newdp[x:] = dp[:-x]
        newdp[:x] = dp[-x:]
        dp = newdp
        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):
m = 2019
s = 0
i = 1
l=[0]*m

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

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

count=[0]*2019
count[0]+=1
sd=0
d=1
for c in s:
   sd+=int(c)*d
   sd%=2019
   d*=10
   d%=2019
   count[sd]+=1

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

print(ans)

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

count=[0]*2019
count[0]+=1
sd=0
d=1
for c in s:
   sd+=int(c)*d
   sd%=2019
   d*=10
   d%=2019
   count[sd]+=1

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

print(ans)

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

mod = 2019

sum_digits = 0

cnts = [0] * (mod + 1)
cnts[0] = 1

d = 1

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

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

print(ans)

Solution (Python):
s = input()
n = len(s)
MOD = 2019
mods = [0] * MOD
mods[0] = 1

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

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

Solution (Python):

def resolve():
    S = input()
    cnts = [0] * 2019
    cnts[0] = 1
    num, d = 0, 1

    for s in S[::-1]:
        num += int(s) * d
        d *= 10
        num %= 2019
        d %= 2019
        cnts[num] += 1

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


if __name__ == "__main__":
    resolve()

Solution (Python):
def main():
    s = input()
    n = len(s)
    dp = [0 for _ in range(2019)]
    dp[0] += 1
    x = 0
    for i in range(n):
        x = (x+int(s[n-1-i])*pow(10,i,2019))%2019
        dp[x] += 1
    ans = 0
    for i in range(2019):
        ans += (dp[i]*(dp[i]-1))//2
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import collections
S = input()
N = len(S)
M = [0]
mod = 0
ten = 1
for s in S[::-1]:
  mod += (int(s) * ten) % 2019
  mod %= 2019
  M.append(mod)
  ten *= 10
  ten %= 2019 
count = collections.Counter(M)
print(sum([c*(c-1)//2 for c in count.values()]))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

s = S()
D = defaultdict(int)
D[0] = 1
ret = 0
ans = 0
j = 1
for i in range(len(s) - 1, -1, -1):
    ret = int(s[i]) * j + ret
    ans += D[ret % 2019]
    D[ret % 2019] += 1
    j = j * 10 % 2019

print(ans)

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

MOD = 2019

mods = [0 for _ in range(2019)]
mods[0] = 1

num = 0
digit = 1
for s in S[::-1]:
  num = s * digit + num
  num %= MOD
  mods[num] += 1
  digit = (digit * 10) % MOD
  
ans = 0
for m in mods:
  ans += m * (m - 1) // 2

print(ans)

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

acc = [0]*(len(s)+1)
digit = 1

for i in reversed(range(0, len(s))):
    si = s[i] * digit % 2019
    acc[i] = (acc[i+1] + si) % 2019
    digit *= 10
    digit %= 2019

cnt = [0]*2019
ans = 0
for i in range(0, len(s)+1):
    ans += cnt[acc[i]]
    cnt[acc[i]] += 1

print(ans)

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

acc = [0]*(len(s)+1)
digit = 1

for i in reversed(range(0, len(s))):
    si = s[i] * digit % 2019
    acc[i] = (acc[i+1] + si) % 2019
    digit *= 10
    digit %= 2019

cnt = [0]*2019
ans = 0
for i in range(0, len(s)+1):
    ans += cnt[acc[i]]
    cnt[acc[i]] += 1

print(ans)

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

Solution (Python):
s = input()
mod = 2019
l = [0]*mod
l[0] = 1 
ans = 0
r = 0
t = 1

for i in s[::-1]:
    r += int(i)*t
    r %= mod 
    l[r] += 1
    t *= 10
    t %= mod 

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

print(ans)

Solution (Python):

s = input()[::-1]

sm = 0

cnts = [0] * 2019
cnts[0] = 1

d = 1

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

ans = 0

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

print(ans)

Solution (Python):
S=input()

N=len(S)
d={}
for i in range(2019):
    d[i]=0

d[0] = 1

mod=0
dig=1

for i in range(N):
    
    
    mod += dig * int(S[N-1-i])
    mod %= 2019
    d[mod] += 1
    dig *= 10
    dig %= 2019


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

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


cnts = [0] * 2019
cnts[0] = 1
mod_num = 0
d = 1

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

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

print(result)

Solution (Python):
S = input()[::-1]
L = len(S)
ans = 0
now = 0
A = [0] * 2019
A[0] = 1
d = 0
for i in range(L):
    now = now + int(S[i]) * pow(10, d, 2019)
    now %= 2019
    d += 1
    A[now] += 1

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

print(ans)

Solution (Python):
from sys import stdin


def get_result(data):
    S = data[0]
    mod_all_bit = [0] * 2019
    mod_all_bit[0] = 1
    
    
    ten_i_mod = [0] * len(S)
    ten_i_mod[0] = 1
    for i in range(len(S)-1):
        ten_i_mod[i+1] = (ten_i_mod[i] * 10) % 2019
    mod = 0
    for i in range(len(S)):
        mod = (mod + ten_i_mod[i] * int(S[-(i+1)])) % 2019
        mod_all_bit[mod] += 1
    ans = 0
    for val in mod_all_bit:
        if val >= 2:
            ans += val * (val-1) * 0.5
    return int(ans)


if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)

Solution (Python):
s = input()

ch = 0
x = 1

rem = [0] * 2019
ans = 0
rem[0] = 1

for c in reversed(s):
    ch = (ch + int(c) * x) % 2019
    x = (x * 10) % 2019
    rem[ch] = rem[ch] + 1

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

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

n = len(s)
dp = [0] * (n + 1)

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

c = Counter(dp)

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

print(ans)

Solution (Python):
import collections
S = list(map(int, input()))[::-1]
mod_list = [0 for _ in range(len(S)+1)]
x = 0
d = 0
for i, s in enumerate(S):
    x += s * pow(10, d, 2019)
    d += 1
    mod_list[i] = x%2019
c = collections.Counter(mod_list)
ans = 0
for i in range(2020):
    ans += c[i] * (c[i]-1)//2
print(ans)

Solution (Python):
S=input()
N=len(S)
Slis=[]
for i in range(N):
  Slis+=[int(S[i])]
T=[0 for i in range(N+1)]


ten=1

for i in range(N):
  T[N-i-1]=(T[N-i]+ten*Slis[N-i-1])%2019
  ten=(ten*10)%2019

MOD=[0 for i in range(2019)]
for i in range(N+1):
  tmp=T[i]%2019
  MOD[tmp]+=1


  
ans=0

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

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

Solution (Python):
from queue import deque


S = deque(input())
mod = 2019
T = [0] * mod
T[0] = 1
a, b = 0, 1

for _ in range(len(S)):
    s = int(S.pop())
    a = a + s * b
    a = a % mod
    T[a] += 1
    b = b * 10
    b = b % mod
    
print(sum((i * (i - 1) // 2 for i in T)))

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

Solution (Python):
from queue import deque
 
    
S = deque(input())
y = 2019
U = [0] * y
t = 0
U[0] = 1
k = 1

for s in reversed(S):
    t = t + int(s) * k
    t %= y
    U[t] += 1
    k *= 10
    k %= y

cnt = 0
for u in U:
    cnt = cnt + u * (u - 1) // 2

print(cnt)

Solution (Python):
S = input()[::-1]
remain_table = [0] * 2019
remain_table[0] = 1
d = 1
chk = 0
for s in S:
    chk += int(s) * d
    chk = chk % 2019
    remain_table[chk] += 1
    d *= 10
    d %= 2019

ans = 0
for r in remain_table:
    ans += r * (r - 1) // 2
print(ans)

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

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

n = len(s)
dp = [0] * (n+1)

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

c = Counter(dp)

ans = 0
for i in c.values():
    ans += i * (i-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):
def main():
    s = input()
    MOD = 2019
    r = [0]*MOD
    r[0] = 1
    z = 0
    t = 1
    for i in reversed(s):
        z = int(i) * t + z
        z %= MOD
        t *= 10
        t %= MOD
        r[z] += 1
    print(sum(i*(i-1)//2 for i in r))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
S = input()
MOD = 2019

cnt = [0] * MOD
cnt[0] = 1

now = 0
ans = 0
for d, n in enumerate(map(int, S[::-1])):
    now = (n * pow(10, d, MOD) + now) % MOD
    ans += cnt[now]
    cnt[now] += 1

print(ans)

Solution (Python):
S = str(input())[::-1]
N = len(S)
mod_list = [0]*2020
mod_list[0] = 1

mod = 2019
tmp = 0

for i in range(N):
    tmp = (tmp + int(S[i])*pow(10,i,mod))%mod
    mod_list[tmp] += 1
    
ans = 0
for i in mod_list:
    ans += i*(i-1)//2
        
print(ans)

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


if __name__ == '__main__':
    main()

Solution (Python):


from collections import defaultdict
d = defaultdict(int)

mod = 2019
s = str(input())[::-1]

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

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

print(ans)

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

for i in s:
    tmp = int(i) * pow(10, d, mod) % mod
    tmp = cnt[-1] + tmp
    cnt.append(tmp % mod)
    d += 1

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

Solution (Python):

import sys


def solve(S: int):
    S =str(S)[::-1]
    MOD = 2019
    mod_l = [int(0)]*2019
    mod_l[0] = 1
    prev = 0
    for x in range(len(S)):
        k = int(S[x]) * pow(10, x, MOD) % MOD + prev
        mod_l[k%2019] += 1
        prev = k%2019

    s = sum([x*(x-1)//2 for x in mod_l])
    print(s)
    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 Counter

S = input()
mods = [0]
num, ten = 0, 1
for n in S[::-1]:
    num += int(n) * ten
    num %= 2019
    mods.append(num)
    ten *= 10
    ten %= 2019

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

Solution (Python):
def main():
    S = list(input())
    N = len(S)
    t = 0
    A = [0] * 2019
    A[0] += 1
    d = 1
    for s in reversed(S):
        d *= 10
        d %= 2019
        t += (int(s) * d)
        t %= 2019
        A[t] += 1
    result = sum([a*(a-1)//2 for a in A])
    print(result)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from math import gcd

S = list(map(int, list(read()[:-1])))
n = len(S)
F = [0] * (n + 1)  
for i in ra(n, 0, -1):
    F[i - 1] = (F[i] + S[i - 1] * pow(10, n - (i - 1), 2019)) % 2019
cnt = Counter(F)
ans = 0
for v in cnt.values():
    ans += v * (v - 1) // 2

print(ans)

Solution (Python):


import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    s = ns()
    n = len(s)
    now = 0
    m = [0] * 2019
    for i in range(n):
        now = (now + int(s[n-i-1]) * pow(10, i, 2019)) % 2019
        
        m[now] += 1
    m[0] += 1
    ans = 0
    for mi in m:
        ans += (mi-1) * mi //2
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter

S = input()
mods = [0]
num, ten = 0, 1
for n in S[::-1]:
    num += int(n) * ten
    num %= 2019
    mods.append(num)
    ten *= 10
    ten %= 2019

counter = Counter(mods)
ret = 0
for v in counter.values():
    ret += v * (v - 1) // 2
print(ret)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque

from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]



s=input().rstrip()
u=list(map(int,list(s)))
u=list(reversed(u))

n=len(u)
beki=[0 for i in range(n)]
beki[0]=1
for i in range(n-1):
    beki[i+1]=(beki[i]*10)%2019

dp=[0 for i in range(n)]
dp[0]=beki[0]*u[0]
for i in range(n-1):
    dp[i+1]=(dp[i]+beki[i+1]*u[i+1])%2019
dp.append(0)

c=Counter(dp)
ans=0
for l in c.values():
    ans+=(l*(l-1))//2
print(ans)

Solution (Python):
s=input()
l=len(s)
ans=0
p=0
a={}
b=-1
c=-1
d=-1
e=-1
q=1
for j in range(l)[::-1]:
    p=(p+int(s[j])*q)%2019
    q*=10
    q%=2019
    if p==0:
        ans+=1
    if a.get(p)!=None:
        ans+=a[p]
    if a.get(p)!=None:
        a[p]+=1
    else:
        a[p]=1
print(ans)

Solution (Python):
from collections import defaultdict
s = input()
n = len(s)
p = 2019
dd = defaultdict(int)
dd[0] = 1
prev = 0
for i in reversed(range(n)):
    prev = (prev+int(s[i])*pow(10, n-i, p)) % p
    dd[prev] += 1
print(sum(v*(v-1)//2 for v in dd.values()))

Solution (Python):
from collections import defaultdict
p = 2019
s = input()
n = len(s)
dd = defaultdict(int)
digits = 0
remainder = 0
for i in reversed(range(n)):
    x = (remainder+int(s[i])*pow(10, digits, p)) % p
    dd[x] += 1
    remainder = x
    digits += 1
ans = 0
for k, v in dd.items():
    if k == 0:
        ans += v
    ans += v*(v-1)//2
print(ans)

Solution (Python):
from collections import defaultdict

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

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

ans = 0

tmp = 0
for i in range(N):
    s = S[N - 1 - i]
    tmp += int(s) * pow(10, i, 2019)
    ans += dic[tmp % 2019]
    dic[tmp % 2019] += 1

print (ans)

Solution (Python):
import sys
from collections import defaultdict
def cnt_multiple(s, p):
    
    n = len(s)
    if p != 2 and p != 5:
        a = []
        t = 1
        for i in range(n-1, -1, -1):
            a.append((ord(s[i])-ord("0")) * t % p)
            t = t * 10 % p
        cum = [0]
        for v in a:
            cum.append((cum[-1] + v) % p)

        dic = defaultdict(int)
        ans = 0
        for v in cum:
            ans += dic[v]
            dic[v] += 1
        return ans
    elif p == 2:
        ans = 0
        for i in range(n):
            if (ord(s[i]) - ord("0")) % 2 == 0:
                ans += i+1
        return ans
    else:
        ans = 0
        for i in range(n):
            if (ord(s[i]) - ord("0")) % 5 == 0:
                ans += i+1
        return ans
s = str(input())
n = len(s)
p = 2019

print(cnt_multiple(s, p))

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

Solution (Python):
from collections import Counter

s = input()
mod = 2019

li = [0]
num = 0
power = 1
for e in s[::-1]:
    num += int(e) * power
    num %= mod
    li.append(num)

    power *= 10
    power %= mod

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

Solution (Python):
s = input()

n = len(s)
amari = [0] * 2019
amari[0] += 1
tmp = 0
digit = 1
for i in range(n):
    tmp += int(s[n-i-1]) * digit
    tmp %= 2019
    amari[tmp] += 1
    digit = (digit * 10) % 2019

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

print(ans)

Solution (Python):
from collections import Counter

N = list(map(int, input()))
MOD = 2019
cnt = 0
M = len(N)
ans = 0
mod_list = [0]
ten = 1

for n in N[::-1]:
    ans += ten*n
    mod_list.append(ans%MOD)
    ten *= 10
    ten %= MOD

SUM = 0
for k,v in Counter(mod_list).items():
    SUM += v * (v-1) /2

print(int(SUM))

Solution (Python):
MOD = 2019
class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self
    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

S=input()
m=[0]*MOD
m[0]=1
now=Mint()
ans=0
for i in range(1,len(S)+1):
    now += Mint(int(S[-i])) * pow(10,i-1,MOD)
    ans += m[now.value]
    m[now.value] += 1
print(ans)

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

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

num = 0
d = 1

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

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

print(ans)

Solution (Python):
import numpy as np
def resolve():
    s = [int(num) for num in input()]

    ten = 1
    num = 0
    mod_table = np.zeros(shape=2019, dtype=int)

    for i in range(len(s)):
        num += s[len(s) - i - 1] * ten
        num %= 2019
        mod_table[num] += 1
        ten = (ten * 10) % 2019

    ans = sum((mod_table * (mod_table - 1)) // 2)
    ans += mod_table[0]
    print(ans)
    
resolve()

Solution (Python):
from collections import Counter


def f(mod):
    ret = [0]
    power = 1
    num = 0
    for i, e in enumerate(s, 1):
        num *= 10
        num += int(e)
        num %= mod

        power *= 10
        power %= mod
        inv = pow(power, mod - 2, mod)

        ret.append(num * inv % mod)

    return ret


s = input()

mod3 = f(3)
mod673 = f(673)

li = [10 * e673 + e3 for e3, e673 in zip(mod3, mod673)]

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

Solution (Python):
def main():
    s = list(map(int, list(input())))
    m = [0]*2019
    num = 0
    ans = 0
    n = len(s)
    ten = 1
    for i in range(n):
        num += s[n-i-1]*ten
        num %= 2019
        m[num] += 1 
        ten = (ten*10)%2019
    for mi in m:
        if mi:
            ans += (mi*(mi-1))//2
    ans += m[0]
    print(ans)
        
if __name__ == "__main__":
    main()

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

s = input().strip()
n = len(s)
cnt = collections.defaultdict(int)
cnt[0] = 1
res = sm = 0
p10 = 1
for d in reversed(s):
	sm = (sm + int(d) * p10) % 2019
	res += cnt[sm]
	cnt[sm] += 1
	p10 = p10 * 10 % 2019
print(res)

Solution (Python):
def main():
    s = input()
    n = len(s)
    s = s[::-1]
    t = [0]*n
    a = [0]*2020
    x = 1
    ans = 0
    for i in range(n):
        if 0 < i:
            t[i] += t[i-1]
        v = int(s[i])
        v *= x
        t[i] += v
        t[i] %= 2019
        ans += a[t[i]]
        if t[i] == 0:
            ans += 1
        a[t[i]] += 1
        x *= 10
        x %= 2019
    print(ans)


if __name__ == "__main__":
    main()

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

Solution (Python):


from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline




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


def II():
    return int(input())

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    
            

    for d in directions:
        nx = d+x
        
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count


S=list(map(int,list(input())[:-1]))


N=len(S)
smod=[0]*N
bef=0
b=1

for i in range(len(S)):
    l=N-i-1
    bef+=(S[l]*(b))%2019
    smod[l]=bef%2019
    
    b=(b*10)%2019
    
cnt=[0]*2020
for sm in smod:
    cnt[sm]+=1

cnt[0]+=1

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

Solution (Python):
import collections
s = list(input())
n = len(s)
mod = [0]*(n+1)
pow10 = 1
for i in range(n):
    mod[i+1] = (mod[i] + int(s[-1-i])*pow10)%2019
    pow10 = pow10*10%2019
d = collections.Counter(mod)
ans = 0
for i in d.values():
    ans += i*(i-1)//2
print(ans)

Solution (Python):



def main():
  s = input().strip()
  x = remain = 0
  remains = [0] * 2019
  k = 1
  for d in map(int, list(s[::-1])):
    x = d * k + remain
    remain = x % 2019
    k = (10 * k) % 2019
    remains[remain] += 1

  print(sum([(remain * (remain - 1)) // 2 for remain in remains]) + remains[0])
  
if __name__=='__main__':
  main()

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

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

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

sum_list = [0]*(n+1)  
_10 = 1
for i in range(1, n + 1):
    sum_list[i] += (sum_list[i-1] + int(s[n-i])*_10 % 2019) % 2019  
    _10 = _10*10 %2019
"""
(s[j]-s[i]/10**i)が区間の整数
区間の整数が2019で割り切れればよい
つまり、(s[j]-s[i]/10**i)≡0 (mod=2019)
ここで10**iと2019(素数)は互いに素なので、
10**iをかけて上の式はs[j]-s[i]≡0 (mod=2019)と同値
s[j]≡s[i] (mod=2019)となる。
"""
c = Counter(sum_list)
ans = 0

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

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

Solution (Python):
S = input()


S = S[::-1]


cs = [0] * (len(S) + 1)


d = 1

for i in range(len(S)):
  
  m = (int(S[i]) * d) % 2019

  
  
  cs[i+1] = (cs[i] + m) % 2019

  
  d *= 10

  
  d %= 2019


res = 0
c = [0] * 2019


for n in cs:
  c[n] += 1


for n in c:
  
  res += n * (n - 1) // 2


print(res)

Solution (Python):
import collections
 
S = input()
l = [0]
a = 0
b = 1

for i in range(1,len(S)+1):
  a = (a+int(S[-i])*b)%2019
  l.append(a)
  b = (b*10)%2019
  

c = collections.Counter(l)
 
rlt = 0
for k in c:
  rlt += c[k]*(c[k]-1)//2

print(rlt)

Solution (Python):
S=input()
n=len(S)
t=[0]*(n+2)
b=[0]*2019
m=0
mod2019_10=[0]*(n+1)

t[n+1]=0
t[n]=int(S[n-1])%2019
mod2019_10[0]=1
for i in range(1,n+1):
    mod2019_10[i]=(mod2019_10[i-1]*10)%2019
for i in range(1,n):
    t[n-i]=(t[n-i+1]+(int(S[n-i-1])*mod2019_10[i])%2019)%2019

for i in range(1,n+2):
    b[t[i]]+=1

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    count = [0] * 2019
    count[0] = 1
    val = 0
    res = 0
    for i, d in enumerate(reversed(input())):
        d = int(d)
        val += d * pow(10, i, 2019)
        val %= 2019
        res += count[val]
        count[val] += 1
    print(res)
resolve()

Solution (Python):
import collections
s = input()

l = [int(s[-1])]
d = 10
for i in range(len(s)-2, -1, -1):
  l.append((l[-1] + int(s[i])*d) % 2019)
  d *= 10
  d %= 2019
c = collections.Counter(l)
ans = 0  
for i in c.values():
  ans += i*(i-1)//2

ans += c[0]

print(ans)