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):
s=input()[::-1]
n=len(s)
p=2019
S=[0 for i in range(n+1)]
ans=[0]*p

x10=1
for j, i in enumerate(s):
  S[j+1]=(S[j]+(x10*int(i)))%p
  x10*=10
  x10%=p
  ans[S[j+1]]+=1

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

Solution (Python):
S = input().strip()
N = len(S)
A = [0 for _ in range(N)]
B = [0 for _ in range(N)]
B[0] = 1
for i in range(1,N):
    B[i] = (B[i-1]*10)%2019
a = 0
for i in range(N-1,-1,-1):
    a = (int(S[i])*B[N-1-i]+a)%2019
    A[i] = a
C = {i:0 for i in range(2019)}
for i in range(N):
    C[A[i]] += 1
cnt = C[0]
for i in range(2019):
    cnt += (C[i]*(C[i]-1))//2
print(cnt)

Solution (Python):
from itertools import accumulate
from collections import Counter


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


s = input()[::-1]
MOD = 2019


rest = []
for i, x in enumerate(s):
    
    if i == 0:
        tmp = 1
    else:
        tmp = tmp * 10 % MOD
    rest.append(int(x) * tmp % MOD)

result = [x % MOD for x in list(accumulate(rest))]


zero = result.count(0)


c = Counter(result)
c = list(c.values())


print(sum([solve(x) for x in c if x >= 2]) + zero)

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








mod=[0]*2019

tmp=0
ten=1



for ii in range(len(s)):
    i=len(s)-ii-1
    if ii==0:
        ten=1
    else:
        ten=(ten*10)%2019

    tmp=((tmp+s[i]*ten)%2019)
    
    
    mod[tmp]+=1

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

ans+=mod[0]

print(ans)

Solution (Python):
s=input()[::-1]
p=2019
ans=[0]*p

x10, S=1, 0
for i in s:
  S+=x10*int(i)
  S%=p
  x10*=10
  x10%=p
  ans[S]+=1

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

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):
from collections import Counter

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

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

S = list(map(int, list(input())))
mod = 2019
lens = len(S)
mods = [0]*lens
cum = 0
for i in range(lens):
    s = S[-i-1]
    cum += s*pow(10, i, mod)
    cum %= mod
    mods[i] = cum
mods += [0]
from collections import Counter
c = Counter(mods)

ans = 0
for num, cnt in c.most_common():
    if cnt<2:
        break
    ans += cnt*(cnt-1)//2
print(ans)

Solution (Python):
S = input()

cs = [0]
r = 1
for c in S[::-1]:
    cs.append((cs[-1] + r*int(c)) % 2019)
    r *= 10
    r %= 2019

from collections import Counter
ctr = Counter(cs)
ans = 0
for v in ctr.values():
    ans += v*(v-1)//2
print(ans)

Solution (Python):



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


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

ans=0
temp=0
p=1
for i in range(len(S)):
    temp+=S[i]*p
    p=p*10%2019
    temp%=2019
    ans+=mod[temp]
    mod[temp]+=1

print(ans)

Solution (Python):
s=list(input())
s.reverse()
mod=2019

n=[0]*len(s)
n[0]=1
cnt=[0]*len(s)
cnt[0]=int(s[0])
ans=[0]*2019
answer=0

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

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

for i in cnt:
  ans[i]+=1

for i in range(len(ans)):
  answer+=(ans[i]*(ans[i]-1))//2

answer+=ans[0]

print(answer)

Solution (Python):
from collections import Counter
S = list(map(int, list(input())))
MOD = 2019

acc_mod = [0]
for i, s in enumerate(S[::-1]):
    acc_mod.append((acc_mod[-1] + s * pow(10, i, MOD)) % MOD)

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

Solution (Python):
s=[int(x) for x in reversed(list(input()))]
n=len(s)
x=[0]*2019
dp = 0
dim = 1
for si in s:
  dp = (dp + si*dim) % 2019
  x[dp] += 1
  dim = dim * 10 % 2019
ans = x[0]
for i in range(2019):
  ans += x[i]*(x[i]-1)//2
print(ans)

Solution (Python):
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

s=input()[::-1]
n=len(s)
a=[0]*2019
a[0]=1
c,d=0,1
for i in s:
    c+=int(i)*d
    c%=2019
    d*=10
    d%=2019
    a[c]+=1
ans=0
for i in a:
    ans+=i*(i-1)//2
print(ans)

Solution (Python):
def main():
    P = 2019
    S = [int(s) for s in input()]
    ans = 0
    if P == 2:
        for i, v in enumerate(S, start=1):
            if v % 2 == 0:
                ans += i
    elif P == 5:
        for i, v in enumerate(S, start=1):
            if v == 0 or v == 5:
                ans += i
    else:
        cnt = [0]*P
        d = 1
        pre = 0
        cnt[pre] += 1
        for v in S[::-1]:
            v *= d
            v += pre
            v %= P
            cnt[v] += 1
            d *= 10
            d %= P
            pre = v

        ans = sum(cnt[i]*(cnt[i]-1)//2 for i in range(P))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
S = input()
dp = [0]*(len(S)+1)
cur = int(S[len(S)-1])
mod_10 = 1
count_num = [0]*2019
count_num[0] += 1
for i in range(len(S)):
    dp[len(S)-i-1] = cur
    count_num[cur] += 1
    mod_10 = (mod_10*10)%2019
    if i <= len(S)-2:
        cur = (cur+int(S[len(S)-i-2])*(mod_10))%2019
ans = 0
for i in range(2019):
    ans += (count_num[i]*(count_num[i]-1))//2
print(ans)

Solution (Python):
s=input()
n=len(s)
d=[0]*2019
d[0]=1
j=1
ans=0
now=0
for i in s[::-1]:
  now=(now+int(i)*j)%2019
  ans+=d[now]
  d[now]+=1
  j*=10
  j%=2019
print(ans)

Solution (Python):
s = input()

len_s = len(s)

current = 0
mod_dict = dict()
mod_dict[0] = 1
for i in range(len_s-1,-1,-1):
    c = s[i]
    current = (current+pow(10,len_s-i-1,2019)*int(c)) % 2019
    if current in mod_dict:
        mod_dict[current] += 1
    else:
        mod_dict[current] = 1

count = 0
for key in mod_dict:
    count+= (mod_dict[key]*(mod_dict[key]-1))//2

print(count)

Solution (Python):
from collections import defaultdict
import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)
S = input()[::-1]
N = len(S)
cnt = [0]*N
tmp = 0
d = defaultdict(int)
d[0] += 1
for i in range(N):
    tmp += int(S[i])*pow(10,i,2019)
    tmp %= 2019
    d[tmp] += 1
ans = 0
for v in d.values():
    if v >= 2:
        ans += C(v,2)
print(ans)

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


l = [0]
num = 0
for i in range(len(S)):
    
    
    
    num += int(S[i]) * pow(10,i,2019)
    l.append(num % 2019)

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

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


l = [0]
num = 0
for i in range(len(S)):
    
    
    
    num += int(S[i]) * pow(10,i,2019)
    l.append(num % 2019)

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

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


l = [0]
num = 0
for i in range(len(S)):
    num += int(S[i]) * pow(10,i,2019)
    l.append(num % 2019)

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

Solution (Python):
from collections import Counter



S = input()[::-1]





X = [0]





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



C = Counter(X)


ans = 0


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

print(ans)

Solution (Python):
from collections import Counter
MOD = 2019
S = input()[::-1]
X = [0]
for i in range(len(S)):
    X.append((X[-1]+int(S[i])*pow(10, i, MOD))%MOD)
C = Counter(X)
ans = 0
for v in C.values():
    ans += v*(v-1)//2
print(ans)

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

S=input().rstrip()
Smod2019=[0]
num = 0
deg = 0
for i in range(len(S)-1,-1,-1):
    num = (num+int(S[i])*pow(10,deg,2019))%2019
    Smod2019.append(num)
    deg += 1
Sc = collections.Counter(Smod2019)

cnt = 0
for val in Sc.values():
    cnt += val*(val-1)//2
print(cnt)

Solution (Python):
S=input()
S=list(reversed(S))

m=2019
cnt=[0 for i in range(m)]

len_S=len(S)
x=1
tot=0
ans=0

for i in range(len(S)):
    cnt[tot]+=1
    tot+=(ord(S[i])-ord('0'))*x
    tot %= m
    ans+=cnt[tot]
    x=x*10%m

print(ans)

Solution (Python):

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

    counts = [0] * 2019
    counts[0] = 1
    res, digit = 0, 1
    for i in S:
        res += int(i) * digit
        res %= 2019
        digit *= 10
        digit %= 2019
        counts[res] += 1

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

def modpow(a, n, m):
	r = 1
	while n > 0:
		if n & 1:
			r = r*a%m
		a = a*a%m
		n >>= 1
	return r

S,r = input(),0
dp = list(range(len(S)+1))
dp[-1],dp[-2] = 0,int(S[-1])

for i in range(3,len(S)+2):
	dp[-i] = (dp[-i+1] + modpow(10,i-2,2019)*int(S[-i+1])) % 2019

for x in Counter(dp).values():
	r += x*(x-1)//2
print(r)

Solution (Python):
from collections import defaultdict
S = input()
l = len(S)
d = {0:0}
mod10n = 1
for i in range(1, len(S)+1):
    s = int(S[l-i])
    d[i] = (d[i-1] + s * mod10n) %2019
    mod10n = (mod10n * 10) % 2019
count_d = defaultdict(int)
for key in d.keys():
    count_d[d[key]] += 1
counter = 0
for key in count_d.keys():
    counter += (count_d[key] * (count_d[key]-1)) //2

print(counter)

Solution (Python):
S = str(input())
N = len(S)
b = [0] * 2019
count = 0
b[0] = 1
t = 0
k = 1

if len(S) < 4:
    print(0)
else:
    t = int(S[-1])
    b[t] += 1
    for i in range(1,N):
        k = k * 10 % 2019
        t = (k * int(S[-i-1]) + t) % 2019 
        b[t] += 1

    for i in b:
        count += i*(i-1)//2

    print(count)

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import Counter
def main():
    s = input()
    n = len(s)

    amari = [0] * n
    ketaamari = 1
    t = 0
    for i1 in range(n):
        t = (t + ketaamari * int(s[-i1 -1])) % 2019
        amari[-i1-1] = t
        ketaamari = (ketaamari * 10) % 2019
    amari.append(0)
    ac = Counter(amari)
    r = 0
    for v in ac.values():
        r += v * (v - 1) // 2
    print(r)

if __name__ == '__main__':
    main()

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

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

Solution (Python):
s=input()
n=len(s)
cnts=[0]*2019

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

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

Solution (Python):
import copy

s = list(input())

s.reverse()
n = len(s)
MOD = 2019
m = [0] * n
msum = [0] * (n+1)
cnt = [0] * (MOD)
cnt[0] = 1
t = 1
for i in range(n):
    m[i] = int(s[i]) * t % MOD
    msum[i+1] = (msum[i] + m[i]) % MOD
    cnt[msum[i+1]] += 1
    t = t * 10 % MOD

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

Solution (Python):
import copy

s = list(input())

s.reverse()
n = len(s)
MOD = 2019
m = [0] * n
msum = [0] * (n+1)
cnt = [0] * (MOD)
cnt[0] = 1
t = 1
for i in range(n):
    m[i] = int(s[i]) * t % MOD
    msum[i+1] = (msum[i] + m[i]) % MOD
    cnt[msum[i+1]] += 1
    t = t * 10 % MOD

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

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    """
    modulos = [0]*2019
    modulos[0] = 1
    S = input()
    base = 1
    num = 0
    for c in S[::-1]:
        num = (base*int(c)+num)%2019
        base = (base*10)%2019
        modulos[num] += 1
    answer = 0
    for n in modulos:
        answer += n*(n-1)//2
    return answer


if __name__ == '__main__':
    print(solve())

Solution (Python):

from collections import defaultdict

S = input()

ctr = defaultdict(int)
ctr[0] = 1
cur = 0
n = len(S)
mod = 2019
for i in reversed(range(n)):
    cur = (cur + int(S[i]) * pow(10, n - i - 1, mod)) % mod
    ctr[cur] += 1

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
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 

from decimal import *



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

l = [0]*2019
z = 1
tmp = 0
for i, s in enumerate(S):
	tmp += s*z
	l[tmp%2019] += 1
	z = z*10%2019

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

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
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 

from decimal import *



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

l = [0]*2019
l[0] = 1

tmp = 0
z = 1

for i, s in enumerate(S):
	tmp += s*z
	z = z*10%2019
	l[tmp%2019] += 1

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

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
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 

from decimal import *



S = input()
n = len(S)
s = [0]
for i, x in enumerate(S):
	s.append(int(S[i])*pow(10, n-i-1, 2019)%2019)

tmp = 0
t = []
for x in s:
	tmp = (tmp+x)%2019
	t.append(tmp)

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

Solution (Python):
s=input()[::-1]
alist=[0]*2019
num1=0
num2=1/10
lens=len(s)
for i in range(lens):
  num2=int(((num2)*10)%2019)
  num1=(num1+int(s[i])*(num2))%2019
  alist[num1]+=1
alist[0]+=1
ans=0
for i in range(2019):
  ans+=alist[i]*(alist[i]-1)//2
print(ans)

Solution (Python):


import sys
readline = sys.stdin.readline
read = sys.stdin.read


s = input()

MOD = 2019
d = [0]*MOD
d[0] = 1
r = 0
t = 1
for i in reversed(s):
    r += int(i)*t
    r %= MOD
    t *= 10
    t %= MOD
    d[r] += 1
    
print(sum(i*(i-1)//2 for i in d))

Solution (Python):
mod = 2019


a = input()
n = len(a)
x = [0] * n

for i in range(n):
    x[n - i - 1] = int(a[i])



ans = 0
cnt = [0] * mod
cnt[0] = 1
s = [0] * (n + 1)
e = 1



for i in range(n):
    s[i + 1] = ((x[i] * e) % mod + s[i]) % mod
    _ = s[i + 1]
    ans += cnt[_]
    cnt[_] += 1
    e = (e * 10) % mod


print(ans)

Solution (Python):
s = input()

ans=0
s=s[::-1]
t=1
ketame=0
amari10=1
kosuu=[1]+[0]*2020
for i in s:
    ketame=(ketame+(int(i)*amari10)%2019)%2019
    amari10*=10
    amari10%=2019
    kosuu[ketame]+=1

for i in range(len(kosuu)):
    if kosuu[i]>0:
        ans+=kosuu[i]*(kosuu[i]-1)/2
    
print(int(ans))

Solution (Python):
from collections import Counter
def main():
    S = input()
    A = [0] * ((n := len(S)) + 1)
    A[1] = (a := int(S[-1])) % 2019
    for i in range(2, n + 1):
        a += pow(10, i - 1, 2019) * int(S[-i])
        A[i] = a % 2019
    c = Counter(A)
    ans = 0
    for v in c.values():
        ans += v * (v - 1) // 2
    print(ans)

if __name__ == '__main__':
    main()

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

S = readline().rstrip()
DIV = 2019

cur = 0
from collections import defaultdict
dic = defaultdict(int)
for i in range(len(S) - 1, -1, -1):
  cur += ((int(S[i]) % DIV) * pow(10, (len(S) - 1 - i), DIV)) % DIV
  cur %= DIV
  dic[cur] += 1

ans = 0

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

print(ans)

Solution (Python):
N = str(input())
n,mods = 0,[1]+[0]*2018
d = 1
for i in reversed(N):
  n = (n+int(i)*d)%2019
  mods[n] += 1
  d = (d*10)%2019

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

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

Solution (Python):
s = input().rstrip()
tmp = 0
pw = 1
from collections import Counter
c = Counter()
c[0] += 1

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

print(sum([v*(v-1)//2 for v in c.values() if v > 1]))

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

T=[0]
for i in range(N):
    p = int(S[-1-i])
    T.append( (T[-1]+ pow(10,i,2019)*p)%2019 )
    
from collections import Counter
ans=0
U=dict(Counter(T))
for num in U:
    ans += U[num]*(U[num]-1)//2
print(ans)

Solution (Python):
from collections import Counter
N = list(input())
M = [0]
S = 0
K = 1
ans = 0

for i in range(len(N)):
    S += int(N[-i-1])*K
    S %= 2019

    K *= 10
    K %= 2019
    M.append(S)

P = Counter(M)
for i in range(2020):ans+=P[i]*(P[i]-1)//2
print(ans)

Solution (Python):
s = list(map(int,input()))
s.reverse()
t = len(s)
mod = 2019

arr = [0] * (t+1)
arr[-2] = s[0]
for i in range(1,t):
    arr[t-i-1] = (arr[t-i] + s[i]*pow(10,i,mod)) % mod

from collections import Counter
arr = Counter(arr)

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

print(ans)

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

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

  
  
  dic = [0]*2019
  dic[0] = 1

  ten = 1
  pre = 0
  for i, s in enumerate(S):
    
    pre = (pre + ten*int(s)) % MOD
    dic[pre] += 1
    ten *= 10
    ten %= MOD

  sum_ = 0
  
  

  for v in dic:
    sum_ += v*(v-1)//2

  print(sum_)


if(__name__ == '__main__'):
  main()

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

Solution (Python):
import sys
import collections


def resolve(in_):
    s = next(in_).strip()
    mod = 2019
    dp = [0] * (len(s) + 1)
    ch0 = ord(b'0')
    for i, b in enumerate(reversed(s), 1):
        dp[i] = (dp[i - 1] + (b - ch0) * pow(10, i, mod)) % mod

    return sum(v * (v - 1) // 2 for v in collections.Counter(dp).values())


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):

def solve():
    s=input().split()[0]
    cnt=[0]*2020
    cnt[0]=1
    m=0
    t=1
    for d in map(int,s[-1::-1]) :
        m=(m+d*t)%2019
        t=(t*10)%2019
        cnt[m]+=1
    return sum([ k*(k-1)//2 for k in cnt])

print(solve())

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

Solution (Python):
from collections import Counter

S = input()

N = len(S)

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



r = sum(m*(m-1)//2 for m in Counter(l).values())
print(r)

Solution (Python):
def main():
    import collections

    S = input()

    mod_list = [0]

    for i in range(len(S)):
        index = len(S) - i - 1
        num = int(S[index])

        mod_list.append((mod_list[-1] + num * pow(10, i, 2019)) % 2019)

    CTR_mod_list = collections.Counter(mod_list).most_common()
    cnt = 0

    for i in range(len(CTR_mod_list)):
        n = CTR_mod_list[i][1]

        if (n == 1):
            break

        cnt += n * (n - 1) // 2

    print(cnt)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter



S = input()[::-1]





X = [0]





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



C = Counter(X)


ans = 0


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

print(ans)

Solution (Python):
from collections import Counter



S = input()[::-1]





X = [0]



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



C = Counter(X)


ans = 0


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

print(ans)

Solution (Python):
from collections import Counter
S = input()
S = S + '0'
mod = 2019
p = [-1] * len(S)
r = 0
d = 1
for i,s in enumerate(S[::-1]):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[i] = r

ans = 0
c = Counter(p)
for k,n in c.most_common():
  if n > 1:
    ans += n*(n-1)//2
  else:break
print(ans)

Solution (Python):
from collections import Counter
S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in S[::-1]:
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1








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

Solution (Python):
from collections import Counter
S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in S[::-1]:
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1








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

Solution (Python):
from collections import Counter
S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1








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

Solution (Python):
S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1

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

Solution (Python):
S = input()
mod = [0 for _ in range(len(S))]
mod[0] = int(S[-1])
for i in range(1, len(S)):
    mod[i] = (mod[i - 1] + pow(10, i, 2019) * int(S[-1 - i])) % 2019
ans = 0
res = [0 for _ in range(2019)]
for i in range(len(S)):
    ans += res[mod[i]]
    res[mod[i]] += 1
print(ans + res[0])

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()


def summarizeList(l):
  sl=sorted(l)

  a=sl[0]
  c=1
  res=[]

  for x in sl[1:]:
    if x==a:
      c+=1
    else:
      res.append([a,c])
      a=x
      c=1
  res.append([a,c])

  return res


def main():
  s=S()
  n=len(s)
  s=s[::-1]

  rl=[0]*(n+1)
  for i,x in enumerate(s):
    rl[i+1]=(int(x)*pow(10,i,2019))%2019

  for i in range(n):
    rl[i+1]+=rl[i]
    rl[i+1]%=2019


  sl=summarizeList(rl)
  

  ans=0
  for x,c in sl:
    ans+=(c*(c-1))//2

  return ans


print(main())

Solution (Python):
N = str(input())
n,mods = 0,[1]+[0]*2018
d = 1
for i in reversed(N):
  n = (n+int(i)*d)%2019
  mods[n] += 1
  d = (d*10)%2019

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

Solution (Python):
from collections import defaultdict

s = input()
d = defaultdict(int)
tmp = 0
for i in range(len(s)):
    tmp += int(s[-i - 1]) * pow(10, i, 2019)
    tmp %= 2019
    d[tmp] += 1

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

print(ans)

Solution (Python):
s = input()

d = [0 for i in range(len(s) + 1)]
i = len(s) - 1
deg = 1
while i >= 0:
    d[i] = (int(s[i]) * deg + d[i + 1]) % 2019
    deg = (deg * 10) % 2019
    i -= 1



cnt = [0 for i in range(2019)]
for i in d:
    cnt[i] += 1

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

print(res)

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


s = readline().decode().rstrip()
s = s[::-1]
n = len(s)
d = [0] * (n)
d[0] = int(s[0]) % mod

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

d = [0] + d

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

Solution (Python):
from collections import Counter
S = input()
S = S[::-1]
N = len(S)
counter = Counter()
counter[0] = 1
prev = 0
MOD = 2019
for i in range(N):
  c = (int(S[i]) * pow(10, i, MOD) )%MOD
  prev = (prev+c)%MOD
  counter[prev] += 1

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


print(ans)

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

MOD = 2019


def main(input, print):
    s = input().strip()
    ans = 0
    cnt = [0] * MOD
    k = 1
    t = 0
    
    cnt[0] = 1  
    for i in reversed(range(len(s))):
        t += int(s[i])*k
        t %= MOD
        ans += cnt[t]
        cnt[t] += 1
        k = k * 10 % MOD
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Solution (Python):
s=input()
p=2019
ans=0
M=[0]*p
M[0]=1
tmp=0
for i in range(len(s)):
    tmp+=(int(s[-i-1])*pow(10,i,p))
    tmp%=p
    ans+=M[tmp]
    M[tmp]+=1
print(ans)

Solution (Python):

from collections import defaultdict

S = input()
n = len(S)

mod = 2019
d = defaultdict(int)
d[0] = 1
num = 0
for i in reversed(range(n)):
    num += int(S[i]) * pow(10, n - i - 1, mod)
    num %= mod
    d[num] += 1

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

Solution (Python):




from collections import Counter


def main():
    S = input()
    A = list(map(int, S))[::-1]
    mod = []
    ten = 10
    for i in range(len(A)):
        if i == 0:
            mod += A[i],
        else:
            mod += (mod[i-1]+ten*A[i])%2019,
            ten = (ten*10)%2019
    mod += 0,

    C = Counter(mod)
    print(sum([c*(c-1)//2 for c in C.values()]))

main()

Solution (Python):

import math
S = input()[::-1]
remainder = [0] * 2019



remainder[0] = 1

num = 0
d = 1
for s in S:
  num += int(s) * d
  remainder[num % 2019] += 1
  d *= 10
  
  
  
  d %= 2019
ans = 0
for i in range(2019):
  ans += remainder[i] * (remainder[i]-1) // 2
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


s = input()
n = len(s)
a = [None]*n
c = 0
v = 1
for i in range(n-1, -1, -1):
    c = (c + v*int(s[i])) % 2019
    a[i] = c
    v *= 10
    v %= 2019
from collections import Counter
cc = Counter(a)
ans = 0
for k,v in cc.items():
    ans += v*(v-1)//2
ans += cc[0]
print(ans)

Solution (Python):
from collections import Counter

s = input()
n = len(s)
digits = [int(c) for c in s[::-1]]
a = [0] * (n + 1)
p = 2019

for i, digit in enumerate(digits):
    a[i + 1] = (digit * pow(10, i, p) + a[i]) % p

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

print(ans)

Solution (Python):


S = input().strip()

num = 0
cnt_mod = {0:1}  
mod = 2019
base_pow = 1

for i in range(len(S)):
    digit = int( S[len(S)-1-i] )
    
    num += (digit * base_pow) % mod
    num %= mod
    
    base_pow = (base_pow * 10) % mod
    
    cnt_mod.setdefault(num, 0)
    cnt_mod[num] += 1


ans = 0

for r,c in cnt_mod.items():
    
    
    if c >= 2:
        ans += c*(c-1)//2

print(ans)

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

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

Solution (Python):
import math
import fractions
import collections
import itertools
from collections import deque
S=input()
N=len(S)
cnt=0
l=[]
"""
cnt=0
p=10**9+7
for i in range(K,N+2):
    cnt=(cnt+((N-i+1)*i)+1)%p
    
print(cnt)
"""
amari=[0]*(N+1)
num=0
for i in range(N):
    num=num+pow(10,i,2019)*int(S[N-1-i])
    amari[i+1]=num%2019

c=collections.Counter(amari)
values=list(c.values())	
key=list(c.keys())	



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

Solution (Python):



S = input()

res = 0

x = 0
p = 1
MOD = 2019
reminder = [0]*2019
reminder[0] = 1
for s in reversed(S):
    """ 累積和 """
    x = (int(s)*p + x)%MOD
    p = p*10%MOD
    res += reminder[x]
    reminder[x] += 1

print(res)

Solution (Python):


import sys
input = sys.stdin.readline


S = input().rstrip()

res = 0

x = 0
p = 1
MOD = 2019
reminder = [0]*2019
reminder[0] = 1
for s in reversed(S):
    """ 累積和 """
    x += int(s)*p
    x %= MOD
    p *= 10
    p %= MOD
    res += reminder[x]
    reminder[x] += 1

print(res)

Solution (Python):


import sys
input = sys.stdin.readline


S = input().rstrip()

res = 0

x = 0
p = 1
MOD = 2019
reminder = [0]*2019
reminder[0] = 1
for s in reversed(S):
    """ 累積和 """
    x = (int(s)*p + x)%MOD
    p = p*10%MOD
    res += reminder[x]
    reminder[x] += 1

print(res)