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,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string


BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")



def main():
    k=2019
    s=str(input())[::-1]
    mod10=[1]
    for i in range(1,len(s)):
        mod10.append((mod10[i-1]%k*10%k)%k)
    inverse=[]
    for i in range(0,len(s)):
        n=int(s[i])
        if n!=0:
            if len(inverse)>0:
                mod=((n%k*mod10[i])%k+inverse[-1])%k
            else:
                mod=((n%k*mod10[i])%k)%k
            inverse.append(mod)
    res=[x for x in list(collections.Counter(inverse).items()) if x[0]==0 or x[1]>1]
    
    
    ans=0
    for r in res:
        if r[0]==0:
            ans+=(r[1]+1)*r[1]//2
        else:
            ans+=(r[1]-1)*r[1]//2
    print (ans)    
    
    
    
    
if __name__ == "__main__":
    main()

Solution (Python):
s = input()

mod = [0] * 2019
mod[0] = 1
d = 1
n = 0
ans = 0

for i in reversed(s):
    n += int(i) * d
    n %= 2019
    d *= 10
    d %= 2019
    mod[n % 2019] += 1

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

print(ans)

Solution (Python):


S = input()[::-1]

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

num, d = 0, 1

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

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

print(ans)

Solution (Python):

from collections import defaultdict

S = input()
N = len(S)
d = defaultdict(int)

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

print(ans)

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

ans = 0
ten = 1
d = 0
cntlist = [0]*2019
cntlist[0] = 1
for i in range(n-1,-1,-1): 
    a = int(s[i])*ten%2019
    d = (d + a)%2019
    ten *= 10
    ten %= 2019
    cntlist[d] += 1

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

print(ans)

Solution (Python):
import sys

IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))

INIT_VAL = 0
MD2 = lambda d1,d2: [[INIT_VAL]*d2 for _ in range(d1)]
MD3 = lambda d1,d2,d3: [MD2(d2,d3) for _ in range(d1)]

DIVC = lambda x,y: -(-x//y)
DIVF = lambda x,y: x//y

def main():
    s = list(map(int, IS()))
    n = len(s)
    p = 2019
    cnt = 0
    d = [0]*p
    d[0] = 1 
    ss = 0
    x = 1
    for si in s[::-1]:
        ss += x*si
        ss %= p
        d[ss] += 1
        x = (10*x)%p 
    cnt = 0
    for di in d:
        cnt += di*(di-1)//2 
    print(cnt)

if __name__ == '__main__':
    main()

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

rem_count = [0] * divisor
rem_count[0] = 1
num = 0
pow10 = 1
total = 0

for digit in reversed(digits):
    num += digit * pow10
    rem = num % divisor
    total += rem_count[rem]
    pow10 *= 10
    rem_count[rem] += 1

    
    num = rem
    pow10 %= divisor

print(total)

Solution (Python):
def main():
    S = input()
    u = 0
    H = [0] * 2019
    H[0] = 1
    m = 1
    r = 0
    for s in reversed(S):
        u = (u + m * int(s)) % 2019
        r += H[u]
        H[u] += 1
        m = (m * 10) % 2019
    return r


print(main())

Solution (Python):
"""
s=1817181712114 なら
4
10
100
2000
10000
700000
1000000
80000000
100000000
7000000000
10000000000
800000000000
1000000000000
の数列とみて, 各々%2019を取ってzero sum range
"""
from collections import Counter
def make_modlist(Len,mod):
    modlist=[0]*Len
    modlist[0]=1
    for i in range(1,Len):
        modlist[i]=10*modlist[i-1]%mod
    return modlist
a=list(map(int,input()))
a.reverse()
n=len(a)
d=make_modlist(n,2019)
b=[0]*(n+1)
for i in range(n):
    b[i+1]=a[i]*d[i]%2019
for i in range(1,n+1):
    b[i]+=b[i-1]
    b[i]%=2019
ans=0
for i in Counter(b).values():
    ans+=i*(i-1)//2
print(ans)

Solution (Python):
s = list(map(int,list(input())))[::-1]
n = len(s)
chk = [0]*2019
chk[0] = 1
t,m,ans = 1,0,0
for i in s:
    m = (m+t*i)%2019
    ans += chk[m]
    chk[m] += 1
    t = t*10%2019
print(ans)

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):
S = input()
digits = list(map(int, S))
divisor = 2019

rem_count = [0] * divisor
rem_count[0] = 1
num = 0
pow10 = 1
total = 0

for digit in reversed(digits):
    num = digit * pow10 + num
    num %= divisor
    total += rem_count[num % divisor]
    pow10 *= 10
    pow10 %= divisor
    rem_count[num % divisor] += 1

print(total)

Solution (Python):
s_l = list(input())
n = len(s_l)


dp_dict = {0:1}
t = 0
x = 1
for i in range(n):
    a = int(s_l[-(i+1)])
    t = (t + a*x)%2019
    x = x*10 %2019
    dp_dict[t] = dp_dict.get(t,0) + 1

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

print(ans)

Solution (Python):
mod = [0]
pw = 1
for c in input()[::-1]:
    
    
    
    
    
    
    
    mod.append((int(c) * pw + mod[-1]) % 2019)
    pw = pw * 10 % 2019
from collections import *





print(sum(v * (v - 1) // 2 for v in Counter(mod).values()))

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

count = [0]*2019
count[0] = 1  

num, d = 0, 1  

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

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

Solution (Python):
S = input()
ans = 0
r = [0] * 2019
r[0] = 1
t = 0
base = 1
for c in S[::-1]:
    t = (t + base * int(c)) % 2019
    base = (base * 10) % 2019
    r[t] += 1

for k in r:
    ans += k * (k - 1) // 2

print(ans)

Solution (Python):
s_l = list(input())
n = len(s_l)


dp_dict = {0:1}
t = 0
for i in range(n):
    a = int(s_l[-(i+1)])
    t = (t + a*(pow(10,i,2019)))%2019
    dp_dict[t] = dp_dict.get(t,0) + 1

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

print(ans)

Solution (Python):
s_l = list(input())
n = len(s_l)


dp_dict = {0:1}
t = 0
for i in range(n):
    a = int(s_l[-(i+1)])
    t = (t + a*(pow(10,i,2019)))%2019
    dp_dict[t] = dp_dict.get(t,0) + 1

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

print(ans)

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

num = 1
l = [0]
for i in range(n-1, -1, -1):
    l.append((l[-1] + int(s[i]) * num) % 2019)
    num *= 10
    num %= 2019

from collections import Counter
dic = Counter(l)

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

Solution (Python):
from collections import defaultdict

s = input()
n = len(s)
t = 0
d = defaultdict(int)
for i in range(1, n + 1):
    t = (t + pow(10, i, 2019) * int(s[-i])) % 2019
    d[t] += 1
c = d[0]
for v in d.values():
    c += v * (v - 1) // 2
print(c)

Solution (Python):
s=list(input())
s=s[::-1]
l=len(s)
mod=2019
count=[0]*2019
count[0]=1
num=0
seki=1
for i in range(l):
    num+=int(s[i])*seki
    num=num%mod
    count[num]+=1
    seki=(seki*10)%mod
ans=0
for i in range(2019):
    N=count[i]
    ans+=N*(N-1)//2
print(ans)

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

cnt = [0] * 2019
cnt[0] = 1

num, d = 0, 1

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

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

print(ans)

Solution (Python):
import collections
s = input()
u = collections.deque([0])
for i in range(len(s)):
    u.append((u[i]+int(s[-i-1])*10**(i%224))%2019)
u2 = collections.Counter(u)
sum = 0
for i in u2.values():
    sum += i*(i-1)/2
print(int(sum))

Solution (Python):

def main():
  s = tuple(map(int, input()[::-1]))

  mod = 2019

  counts = [0] * mod
  counts[0] = 1
  t = 0
  x = 1
  for i in range(len(s)):
    t = (t + s[i] * x) % mod
    counts[t] += 1
    x = (x * 10) % mod

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

  print(ans)

main()

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

cnts = [0] * 2019

cnts[0] = 1

sum_of_digits = 0

d = 1

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

ans = 0

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

print(ans)

Solution (Python):

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

  mod = 2019

  counts = [0] * mod
  counts[0] = 1
  t = 0
  x = 1
  for num in s:
    t = (t + num * x) % mod
    counts[t] += 1
    x = (x * 10) % mod

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

  print(ans)

main()

Solution (Python):
mod = [0]
pw = 1
for c in input()[::-1]:
    mod.append((int(c) * pw + mod[-1]) % 2019)
    pw = pw * 10 % 2019
from collections import *
print(sum(v * (v - 1) // 2 for v in Counter(mod).values()))

Solution (Python):
S = input()
mod = [0]
for d, c in enumerate(S[::-1]):
    mod.append((int(c) * pow(10, d, 2019) + mod[-1]) % 2019)
from collections import *
print(sum(v * (v - 1) // 2 for v in Counter(mod).values()))

Solution (Python):
S = input()

cs = {0: 1}

result = 0

n = 0
for i in range(len(S)):
    c = int(S[-i-1])
    n += c * pow(10, i, 2019)
    m = n % 2019
    if m in cs:
        result += cs[m]
        cs[m] += 1
    else:
        cs[m] = 1

print(result)

Solution (Python):
n=list(map(int,input()))
d=[0]*2019
d[0]=1
a=0
b=len(n)
for i in reversed(range(b)):
    a+=(n[i]*pow(10,(b-i-1),2019))
    a%=2019
    d[a]+=1

ans=0

for i in range(2019):
    c=d[i]
    ans+=c*(c-1)//2
        
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):
n=list(map(int,input()))
d=[0]*2019
d[0]=1
a=0
b=len(n)
for i in reversed(range(b)):
    a+=(n[i]*pow(10,(b-i-1),2019))
    a%=2019
    d[a]+=1

ans=0

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

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

def calc(S):
    N = len(S)
    r = 0
    d = [0] * 2019
    p = 1
    d[0] = 1
    for i in range(N):
        r = (r + int(S[N - 1 - i]) * p) % 2019
        p = (p * 10) % 2019
        d[r] += 1
    ans = 0
    for c in d:
        ans += c * (c - 1) // 2
    return ans


S = input()
print(calc(S))

Solution (Python):
from collections import Counter
MOD=2019
S=input();N=len(S)
Cum=[0]*(N+1)
for i in range(N):
    Cum[i+1]=(Cum[i]+int(S[N-i-1])*pow(10,i,MOD))%MOD
res=0
c=Counter(Cum).most_common()
for a,b in c:
    res+=b*(b-1)//2
    if(b==1):
        break
print(res)

Solution (Python):
from collections import Counter

s = list(map(int, list(input())))[::-1]
N = len(s)
cusum = [0]*(N+1)
cusum[0] = s[0] % 2019
for i in range(1, N):
    power = pow(10, i, 2019)
    cusum[i] = (cusum[i-1] + power * s[i]) % 2019
counter = Counter(cusum)
print(sum(x*(x-1)//2 for x in counter.values()))

Solution (Python):
from collections import defaultdict
dd = defaultdict(int)
S = list(input().rstrip())
tmp = 0
dd[0]+=1
r=1
for s in S[::-1]:
    tmp+=int(s)*r
    r*=10

    tmp%=2019
    r%=2019
    dd[tmp]+=1
su=0
for i in dd.values():
    su+=(i*(i-1))//2
print(su)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

s = [int(i) for i in STR()]
l = len(s)
arr = [-1 for _ in range(l)]
tmp = 0
for i in range(l):
    tmp += s[i] * pow(10, l - i, 2019)
    tmp %= 2019
    arr[i] = tmp
arr.sort()
tmp = arr[0]
cnt = 1
ans = 0
for i in range(1, l):
    if tmp == arr[i]:
        cnt += 1
    else:
        ans += cnt * (cnt - 1) // 2
        if tmp == 0:
            ans += cnt
        cnt = 1
        tmp = arr[i]
ans += cnt * (cnt - 1) // 2
if tmp == 0:
    ans += cnt
print(ans)

Solution (Python):
f=[0]*22209
def main():
    a=list(map(int,input()))
    n=len(a)
    ans=0
    d=[0]*2019
    d2=[0]*2019
    d2[a[0]]+=1
    for i in range(11):
        for j in range(2019):
            f[2019*i+j]=j
    for i in range(1,n):
        d[a[i]]+=1
        for j in range(2019):
            d[f[10*j+a[i]]]+=d2[j]
        ans+=d[0]
        for j in range(2019):
            d2[j]=d[j]
            d[j]=0
    print(ans)
main()

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

def main():
    S = [int(i) for i in readline().strip()[::-1]]

    a = {}
    a[0] = 1
    t = 0
    x = 1
    for s in S:
        t += s * x
        t %= 2019
        
        if t in a:
            a[t] += 1
        else:
            a[t] = 1

        x *= 10
        x %= 2019
    
    ans = 0
    for v in a.values():
        ans += v * (v-1) // 2
    
    print(ans)
    

if __name__ == "__main__":
    main()

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

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

d = 1

for c in s:
    sum_of_digits += int(c) * d
    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


def comb(n):
    return n * (n-1)/2


s = input()
ans = 0
lst_mod = [0]*2019  
lst_mod[0] += 1
num, dim = 0, 1
for char in reversed(s):
    num += int(char)*dim
    num %= 2019
    dim *= 10
    dim %= 2019  
    lst_mod[num] += 1

for mod in lst_mod:
    ans += comb(mod)
print(int(ans))

Solution (Python):
S = input()
ans = 0
mods = [0] * 2019
mods[0] = 1
curr = 0
x = 1
for d in reversed(S):
    curr = (curr + int(d) * x) % 2019
    ans += mods[curr % 2019]
    mods[curr % 2019] += 1
    x = x * 10 % 2019
print(ans)

Solution (Python):
s=input()[::-1]
ans=0
u=0
d=1
l=[0]*2019
l[0]=1
for i in map(int,s):
  u=(u+(i*d)%2019)%2019
  l[u]+=1
  d=d*10%2019
for i in l:
  ans+=i*(i-1)//2
print(ans)

Solution (Python):
from collections import Counter
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    S = readline().strip()[::-1]
    N = len(S)

    a = [0]
    s = 0
    for i in range(N):
        s += int(S[i]) * pow(10, i, 2019)
        a.append(s % 2019)
    
    t = Counter(a)

    ans = 0
    for _, v in t.items():
        ans += v * (v-1) // 2
    
    print(ans)
    

if __name__ == "__main__":
    main()

Solution (Python):
s=input()[::-1]
ans=0
u=0
d=1
l=[0]*2019
l[0]=1
for i in map(int,s):
  u=(u+i*d)%2019
  l[u]+=1
  d=d*10%2019
for i in l:
  ans+=i*(i-1)//2
print(ans)

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

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

num, d = 0, 1

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

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

print(ans)

Solution (Python):
S = list(map(int, list(input())))
N = len(S)
MOD = 2019
DP = [0] * MOD
DP[0] = 1

t = 0
p = 1
for i in range(N):
  k = S[-1 - i]
  t = (t + k * p) % MOD
  DP[t] += 1
  p = p * 10 % MOD

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

print(ans)

Solution (Python):
S = list(input())
N = len(S)
S = [int(s) for s in S]
S = S[::-1]
l = [0] * 2019
index = 0
tmp = 0
z = 1
for i, s in enumerate(S):
    tmp += s * pow(10, i, 2019)
    l[tmp%2019] += 1

ans = l[0]

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

Solution (Python):

s=input()[::-1]
n=len(s)
cnt=[0]*2020
res=0
t=0
p=1
for c in s:
 c=int(c)
 t=(t+c*p)%2019
 p=(p*10)%2019
 cnt[t]+=1
res+=(cnt[0]+1)*cnt[0]//2
for i in cnt[1:]:
 res+=i*(i-1)//2
print(res)

Solution (Python):
s_inv = str(input())[::-1]
dp = [1]+[0]*2018
MOD = 0
ans = 0
num = 0
k = 1

for i in range(len(s_inv)):
  num+=int(s_inv[i])*k
  MOD = num % 2019
  dp[MOD] += 1
  k = k*10
  k %= 2019
for i in dp:
  ans += i*(i-1)/2

print(int(ans))

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

dp = [0] * 2019
now_mod = 0
digit = 1

for i_s in S_reverse:
    now_mod = (now_mod + int(i_s)*digit) % 2019
    digit = (digit*10) % 2019
    dp[now_mod] += 1

ans = sum(x*(x-1)//2 for x in dp)
ans += dp[0]

print(ans)

Solution (Python):




from functools import lru_cache 











S = input()[::-1]

MOD = 2019
tmp = [0]*MOD
tmp[0] += 1
tens = 1
num = 0
for s in S:
    num += int(s) * tens
    num = num % MOD
    tmp[num] += 1
    tens *= 10
    tens %= MOD

ans = 0
for i in tmp:
    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
    num = sum_of_digits % 2019
    d *= 10
    d %=2019
    cnts[num] += 1
 
ans = 0
    
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2
 
print(ans)

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

cnts = [0]*2019
cnts[0] = 1
num = 0
d = 1
ans = 0

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

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

print(ans)

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

counts = [0] * 2019
n, d = 0, 1

for s in S[::-1]:
    n += int(s) * d
    d *= 10
    n %= 2019
    d %= 2019
    counts[n] += 1
ans = counts[0]
for count in counts:
    ans += count * (count - 1) // 2
print(ans)

Solution (Python):
S = input()
N = len(S)
mod = 2019
d = [0] * mod
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):
S = input()
s = list(S)
for i in range(len(s)):
    s[i] = int(s[i])
p = []
p.append(s[len(s)-1])
for i in range(1,len(s)):
    p.append((p[i-1]+s[len(s)-i-1]*pow(10,i,2019))%2019)
p.sort()
u = 0
for i in range(len(p)):
    if p[i] == 0:
        u = u+1
    else:
        break
r = 1
q = []
for i in range(len(p)-1):
    if p[i] == p[i+1]:
        r = r+1
    else:
        if r > 1:
            q.append(r)
            r = 1
q.append(r)
w = 0
for i in range(len(q)):
    w = w + int(q[i]*(q[i]-1)/2)
print(w+u)

Solution (Python):
import sys
import math
from collections import deque
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
def I(): 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 S(): return sys.stdin.readline()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h,w): return [[i for j in range(w)] for k in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)


S = input()
num = [0]*(len(S)+1)
p = 1
d = {}
d[0] = 1
for i in range(len(S)-1,-1,-1):
    num[i] = int(S[i])*p + num[i+1]
    p = p*10%2019
    mod = num[i]%2019
    d[mod] = d.get(mod,0)+1
ans = 0
for i in d:
    m = d[i]
    ans += int(m*(m-1)/2)
print(ans)

Solution (Python):
s=input()

mod=2019
tc=[0]*2019

lens=len(s)

tc[0]=1
tim=0
p10=1
for i in range(len(s)-1,-1,-1):
    ti=(tim+int(s[i])*p10)%mod
    tc[ti]+=1

    tim=ti
    p10=p10*10%mod






    
tsum=0
for i in tc:
    tsum+=(i*(i-1))//2
    
print(tsum)

Solution (Python):
s = input()
n = len(s)
dp = [1] + [0]*2019
now = 0
i = 1

for c in reversed(s):
    now = (now+i*int(c))%2019
    dp[now] += 1
    i = (i*10)%2019

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

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))


p = 2019
s = input()[::-1]
res = 0
now = 0
d = [0] * p
d[0] = 1
for i,t in enumerate(s):
    now += int(t) * pow(10,i,p)
    now %= p
    d[now] += 1
for i in range(p):
    v = d[i]
    res += v*(v-1)//2
print(res)

Solution (Python):
s = input()
n = len(s)
dp = [1] + [0]*2019
now = 0
i = 1

for c in reversed(s):
    now = (now+i*int(c))%2019
    dp[now] += 1
    i *= 10
    i %= 2019

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

Solution (Python):
def main():
    S=input()
    a=0 
    b=[0]*2019
    No=[0]*2019
    for i in S:
        l=No.copy()
        k=int(i)
        for j in range(2019):
            l[(j*10+k)%2019]=b[j]
        l[k]+=1
        a+=l[0]
        b=l
    print(a)
main()

Solution (Python):


def main():
    from functools import reduce
    import collections
     
    S = list(map(int,input().rstrip()))
    N=len(S)
    mod_list = [0]
    for i in range(1,N+1):
        new1 =pow(10,i-1,2019)
        new = (new1*S[-i]+mod_list[-1])%2019
        
        mod_list.append(new)
        
    count = collections.Counter(mod_list)
    ans =0
    for j in range(2019):
        n = count[j]
        ans+= n*(n-1)/2
    print(int(ans))
if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict


def solve(li):
    cnt = defaultdict(int)
    cnt[0] = 1
    rem = 0
    ans = 0
    for k, i in enumerate(li):
        rem = (rem + i * pow(10, k, 2019)) % 2019
        ans += cnt[rem]
        cnt[rem] += 1
    return ans


print(solve(map(int, input()[::-1])))

Solution (Python):
s = input()[::-1]
cnt = [0] * 2020
cnt[0] = 1
tens = 1
rem = 0
ans = 0
for c in s:
    rem = (rem + (ord(c) - ord('0')) * tens) % 2019
    ans += cnt[rem]
    cnt[rem] += 1
    tens = tens * 10 % 2019
print(ans)

Solution (Python):
from collections import Counter

s = input()
a = [0]
mod = 2019

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

ans = 0
for i in b.values():
    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
from collections import defaultdict 
def main():
    s = input() 
    n = len(s)
    T = [0]
    P = 2019
    dd = defaultdict(int) 
    dd[0] += 1
    for i in range(1, n+1):
        x = (int(s[-i])*pow(10, i-1, P) + T[i-1])%P
        T.append(x)
        dd[x] += 1
    ans = 0
    for i in dd.values():
        ans += i*(i-1)//2
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter 
from collections import defaultdict 

def main():
    s = input() 
    n = len(s)
    T = [0]
    P = 2019
    dd = defaultdict(int) 
    dd[0] += 1
    for i in range(1, n+1):
        x = (int(s[-i])*pow(10, i-1, P) + T[i-1])%P
        T.append(x)
        dd[x] += 1
    ans = 0
    for i in dd.values():
        ans += i*(i-1)//2
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
S = list(input())[::-1]
L = len(S)
from collections import defaultdict

mod = 2019
t = 0
dic = defaultdict(int)
ans = 0
for l in range(L):
    t += pow(10, l, mod)*int(S[l])%mod
    t %= mod
    ans += dic[t]
    dic[t] += 1
    if t==0:
        ans += 1

print(ans)

Solution (Python):
from collections import Counter

S = list(map(int,list(input())))
S.reverse()
N = len(S)
L = [0]
power = 1
for i in range(N):
    L.append((L[-1] + S[i] * power) % 2019)
    power *= 10
    power %= 2019
count = Counter(L)
ans = 0
for value in count.values():
    ans += value * (value - 1) // 2
print(ans)

Solution (Python):
from collections import defaultdict

if __name__ == '__main__':
    MOD = 2019
    strS = input()
    S = [int(s) for s in strS]
    N = len(S)

    mods = defaultdict(int)
    mods[0] += 1
    pow10_mod = 1
    prv_mod = 0
    for idx, s in enumerate(S[::-1]):
        tmp_mod = (prv_mod + s * pow10_mod) % MOD

        mods[tmp_mod] += 1
        pow10_mod = (pow10_mod * 10) % MOD
        prv_mod = tmp_mod

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

    print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import Counter
MOD = 2019

def main():
    S = list(map(int, list(readline().rstrip())))
    N = len(S)
    T = [0] * (N+1)
    e = 1
    for i in range(N-1, -1, -1):
        T[i] = (T[i+1] + S[i] * e) % MOD
        e = e * 10 % MOD
    
    c = Counter(T)
    ans = 0
    for k, v in c.items():
        ans += (v * (v-1)) // 2
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import collections
S = input()
a = []
num = 0
for i,j in enumerate(S[::-1]):
    num += int(j)*(pow(10,i,2019))
    a.append(num%2019)


A = collections.Counter(a)


ans = 0
for i in A.values():
    if i>=2:
        ans += int(i*(i-1)/2)

ans += A[0]
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import Counter
MOD = 2019

def main():
    S = list(map(int, list(readline().rstrip())))
    N = len(S)
    T = [0] * (N+1)
    e = 1
    for i in range(N-1, -1, -1):
        T[i] = (T[i+1] + int(S[i]) * e) % MOD
        e = e * 10 % MOD
    
    c = Counter(T)
    ans = 0
    for k, v in c.items():
        ans += (v * (v-1)) // 2
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import Counter
MOD = 2019

def main():
    S = list(map(int, list(readline().rstrip())))
    N = len(S)
    T = [0] * (N+1)
    e = 1
    for i in range(N-1, -1, -1):
        T[i] = (T[i+1] + int(S[i]) * e) % MOD
        e = e * 10 % MOD
    
    T = [t % MOD for t in T]
    c = Counter(T)
    ans = 0
    for k, v in c.items():
        ans += (v * (v-1)) // 2
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
s=input()
l=len(s)
amari=[0]*2019
amari[0]=1

d=0
digi=1

for c in s[::-1]:
    d=(int(c)*digi + d)%2019
    amari[d]+=1
    digi=(digi*10)%2019

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

Solution (Python):
S = input()
dp = [0 for i in range(2019)]
dp[0] = 1

num = 0
for i,j in enumerate(S[::-1]):
    num += int(j)*(pow(10,i,2019))
    dp[num%2019] += 1

ans = 0
for m in dp:
    if m >= 2:
        ans += int(m*(m-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

MOD = 2019

def solve(S):
    dp = np.zeros(MOD, np.int64)
    temp = np.empty_like(dp)
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % MOD
        temp[x:] = dp[:-x]
        temp[:x] = dp[-x:]
        dp, temp = temp, dp
        answer += dp[0]
        pow10 *= 10
        pow10 %= MOD
    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()
counts =[0] * 2019
counts[0] = 1
num, d = 0,1

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

ans = 0
for count in counts:
  ans += count * (count - 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))