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
input = sys.stdin.readline
from collections import *

S = input()[:-1]
cnt = defaultdict(int)
cnt[0] = 1
ans = 0
now = 0

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

print(ans)

Solution (Python):
from collections import Counter
s = list(map(int,list(input())))

t = 0
cusum = []
for i in range(len(s))[::-1]:
  t += s[i]*pow(10,len(s)-i-1,2019)
  t %= 2019
  cusum.append(t)
  
counter = Counter(cusum)

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

print(ans)

Solution (Python):
from collections import Counter
s = list(map(int,list(input())))

t = 0
cusum = []
for i in range(len(s))[::-1]:
  t += s[i]*pow(10,len(s)-i-1,2019)
  t %= 2019
  cusum.append(t)
  
counter = Counter(cusum)

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

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 9)
MOD = 2019

from collections import defaultdict

S = list(input())
dic = defaultdict(int)
dic[0] += 1

ans = 0
x = 0
count = 0
for s in S[::-1]:
    x += int(s) * pow(10, count, MOD)
    x %= MOD
    ans += dic[x]
    dic[x] += 1
    count += 1

print (ans)

Solution (Python):
from collections import defaultdict
S = input()
N = len(S)

memo = defaultdict(int)
memo[0] += 1

mod = 2019
d = 1
val = 0

for s in S[::-1]:
    s = int(s)
    val += s * d
    val %= mod
    memo[val] += 1
    d *= 10
    d %= mod

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

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

cnt = [0] * M
cnt[0] = 1
N = 0
ans = 0
for i, n in enumerate(map(int, S[::-1])):
    N = (N + n * pow(10, i, M)) % M
    ans += cnt[N]
    cnt[N] += 1
print(ans)

Solution (Python):
def main():
    S = input()
    n = len(S)
    p = 2019 
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    S = [S[i] for i in range(n-1,-1,-1)]
    
    modp_counter = [0] * p
    modp = 0
    modp_counter[0] = 1 
    pair_count = 0
    d = 1
    for s in S:
        modp = (int(s)*d%p+modp)%p
        pair_count += modp_counter[modp]
        modp_counter[modp] += 1
        d *= 10
        d %= p 
    print(pair_count)


main()

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

cs_mods = {0:1}
cumsum = 0
count = 0
for i, s in enumerate(S[::-1]):
    cumsum = (cumsum + int(s) * pow(10, i, mod)) % mod
    cs_mods.setdefault(cumsum, 0)
    
    cs_mods[cumsum] += 1


for k, v in cs_mods.items():
    count += v*(v-1)//2

print(count)

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

mod = 2019
ans = 0
d = 0
L = [0]
memo = [0]
for i in s:
    S =str(i)
    tmp = int(S)*pow(10,d,mod)%mod
    tmp = L[-1] + tmp
    L.append(tmp%mod)
    d +=1

from collections import Counter
L = Counter(L)

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

Solution (Python):
def solve(s):
    mod = 2019
    counts = [0]*mod
    counts[0] = 1
    result = 0
    suffix = 0
    power_of_ten = 1
    for char in s[::-1]:
        digit = int(char)
        suffix = (suffix + digit*power_of_ten) % mod
        result += counts[suffix]
        counts[suffix] += 1
        power_of_ten = 10 * power_of_ten % mod

    return result


if __name__ == "__main__":
    print(solve(input()))

Solution (Python):
def main():
    mod = 2019
    count = [0] * 2019
    count[0] = 1
    s = input().strip()
    digit = 1
    current = 0
    for c in s[::-1]:
        current = (current + int(c) * digit) % mod
        count[current] += 1
        digit = digit * 10 % mod
    return sum([n * (n - 1) // 2 for n in count if n > 1])


print(main())

Solution (Python):
S=input()

p,q=0,1
dp = {0:1}
mod = 2019

for i in range(len(S)-1,-1,-1):
  p = (p+int(S[i])*q)%mod
  if p not in dp:dp[p]=0
  dp[p]+=1
  q= (q*10)%mod

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

Solution (Python):
s=input()
a=[0]*2019
a[0]+=1
pot=1
v=0
ans=0
for i in range(len(s)-1,-1,-1):
	digit=int(s[i])
	v=(v+digit*pot)%2019
	pot=(pot*10)%2019
	ans+=a[v]
	a[v]+=1

print(ans)

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

N = len(S)

A=[0]*2019
number=0
A[0]=1

d=1

ans=0

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

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

print(ans)

Solution (Python):

from collections import defaultdict
string = input()
n = len(string)


string = string[::-1]



S = [0]
d = 10
for i in range(n):
    t = int(string[i])*d+S[i]
    t = t % 2019
    S.append(t)
    d = (d * 10) % 2019


count = 0
d = defaultdict(int)
for key in S:
    d[key] += 1



for j in d.values():
    if j >=2:
        count += j*(j-1)//2






print(count)

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

Solution (Python):
S = input()
S = S[::-1]
d = 1
mods = [0]
counter = [0]*2019
counter[0] += 1
for s in S:
  s = int(s)
  mods.append((mods[-1]+s*d)%2019)
  counter[mods[-1]] += 1
  d *= 10
  d %= 2019

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

Solution (Python):
S = input()
S = S[::-1]
d = 1
mods = [0]
counter = [0]*2019
counter[0] += 1
result = 0
for s in S:
  s = int(s)
  mods.append((mods[-1]+s*d)%2019)
  counter[mods[-1]] += 1
  result += counter[mods[-1]] - 1
  d *= 10
  d %= 2019

print(result)

Solution (Python):
from collections import Counter
mod = 2019
s = list(input())
ln = len(s)

ms = [0]*(ln+1)
ms[ln] = 0
cr = 1
for i in range(ln):
  ms[ln-1-i] = (ms[ln-i] + cr*int(s[ln-1-i])) % mod
  cr = (cr*10) % mod

cnts = Counter()
for i in ms:
  cnts[i] += 1
ans = 0
for k,v in cnts.items():
  if v >= 2:
    ans += int(v*(v-1)/2)
print(ans)

Solution (Python):
m = 2019
C = [0]*m
C[0] = 1
s = list(input())
now = 0
cnt = 0
while s:
  now += pow(10, cnt, m) * int(s.pop())
  now %= m
  C[now] += 1
  cnt += 1
ans = 0
for c in C:
  ans += c*(c-1)//2
print(ans)

Solution (Python):
s=input()
n=len(s)
mod=2019
sum=0
p=1
d={}
d[0]=1
for i in range(n-1,-1,-1):
    sum=(sum+int(s[i])*p)%mod
    if sum in d:
        d[sum]+=1
    else:
        d[sum]=1
    p=(p*10)%mod
ans=0
for v in d.values():
    ans+=(v*(v-1))//2
print(ans)

Solution (Python):
s = input()
n = len(s)
res = 0
sum = 0
c = {}
c[0] = 1
p = 1
for i in range(n - 1, -1, -1):
    sum = (sum + int(s[i]) * p) % 2019
    if sum in c:
        res += c[sum]
    p = (p * 10) % 2019
    c[sum] = c.get(sum, 0) + 1

print(res)

Solution (Python):
s = input()
d={0:1}
suf=0
pot=1
ans=0
for i in range(len(s)-1,-1,-1):
    dig=int(s[i])
    suf=(suf+dig*pot)%2019
    pot=(pot*10)%2019
    if suf in d:
        ans+=d[suf]
        d[suf]+=1
    else:
        d[suf]=1
print(ans)

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

l = [0 for i in range(2019)]
n = len(s)
l[0] = 1
prev = 0
digit = 1
for c in s:
    t = (int(c) * digit + prev) % 2019
    l[t] += 1
    digit = (digit * 10) % 2019
    prev = t

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

print(res)

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


import sys
import itertools
import collections

INF = 1145141919


def solve(S: int):
    l = list(reversed(str(S)))
    a = [int(l[c]) * pow(10, c, 2019) for c in range(len(l))]

    def list_cumsum(l):
        return list(itertools.accumulate(l))
    s = [n % 2019 for n in list_cumsum([0]+a)]

    return sum([sum(range(v)) for v in collections.Counter(s).values()])


def main():

    sys.setrecursionlimit(10 ** 6)

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


if __name__ == '__main__':
    main()

Solution (Python):


import sys
import itertools
import collections

INF = 1145141919


def solve(S: int):
    l = list(reversed(str(S)))
    a = [int(l[c]) * pow(10, c, 2019) for c in range(len(l))]

    def list_cumsum(l):
        return list(itertools.accumulate(l))
    s = [n % 2019 for n in list_cumsum([0]+a)]

    return sum([int(v * (v-1) / 2) for v in collections.Counter(s).values()])


def main():

    sys.setrecursionlimit(10 ** 6)

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


if __name__ == '__main__':
    main()

Solution (Python):
def function(S):
    S = S[::-1]
    mods = [0]*2019 
    mods[0] += 1 
    
    
    num = 0
    digit = 1
    for c in S:
        num = (int(c) * digit + num) % 2019
        digit = (digit * 10) % 2019
        mods[num] += 1
    
    result = 0
    for m in mods:
        result +=  m * (m-1) // 2

    return str(result)

if __name__ == '__main__':
    print(function(input()))

Solution (Python):
from collections import defaultdict

s=input()
d=defaultdict(int)

dp=0
d[0]+=1
r=1
for i in range(len(s)-1,-1,-1):
	dp+=int(s[i])*r
	dp%=2019
	d[dp]+=1
	r*=10
	r%=2019
	
res=0

l=list(d.values())
for a in l:
	res+=a*(a-1)//2
	
print(res)

Solution (Python):
s=input()

d=[0]*2019
dp=0
d[0]+=1
l=len(s)
r=1

for i in range(l):
	dp+=int(s[l-1-i])*r
	dp%=2019
	r*=10
	r%=2019
	d[dp]+=1

res=0

for a in d:
	res+=a*(a-1)//2
	
print(res)

Solution (Python):
s = list(input())
mods = [0]*(len(s))
countRemainder = [0] * 2019
cnt = 0


m = 1
mod = 0
for i in range(len(s)):
    mod += int(s[len(s) - i - 1]) * m

    mod %= 2019
    m *= 10
    m %= 2019

    countRemainder[mod] += 1

countRemainder[0] += 1

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

print(cnt)

Solution (Python):
s = input()[::-1]
a = 0
cnt = [0]*2019
cnt[0] = 1
d = 1
for c in s:
    a += int(c) * d
    a %= 2019
    d *= 10
    d %= 2019
    cnt[a] += 1





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

print(ans)

Solution (Python):
S = input()
N = len(S)
SUM = [0] * (N + 1)
MOD = 2019

r = 1  
S = S[::-1]
for i in range(N):
    A = r * int(S[i])
    SUM[i + 1] = (SUM[i] + A) % MOD
    r = r * 10 % MOD

cnt = [0] * 2019
ans = 0
for x in SUM:
    ans += cnt[x]
    cnt[x] += 1
print(ans)

Solution (Python):
def main():
    mod=2019
    S=input()[::-1]
    l=[0]
    m=1
    for i in range(len(S)):
        l.append((l[-1]+m*int(S[i]))%mod)
        m=m*10%mod
    ll=[0]*2019
    for i in l:
        ll[i]+=1
    ans=0
    for i in range(2019):
        ans+=ll[i]*(ll[i]-1)//2
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
mod = 2019
s = input()
n = len(s)
w = 0
d = [0] * mod
p = 1
for i in reversed(range(n)):
	w += int(s[i]) * p
	p *= 10
	p %= mod
	w %= mod
	d[w] += 1
d[0] += 1
o = 0
for x in d:
	o += x * (x - 1) // 2
print(o)

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 = input()[::-1]
N = len(S)
l = [0]*2019
l[0] = 1
n = 0
d = 1

for i in range(N):
    n += int(S[i]) * d
    r = n % 2019
    l[r] += 1
    d = 10*d % 2019
    
out = 0    
for m in l:
    out += (m*(m-1))//2 
print(out)

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

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

Solution (Python):
import sys
import collections as coun
sys.setrecursionlimit(10000000)
s=input()
n=len(s)
def mod10(x):
    return (10**(x%224))%2019
dp=[-1]*n
tmp=0
for i in reversed(range(n)):
    if i==n-1:
        dp[i]=int(s[i])
    else:
        dp[i]=(dp[i+1]+int(s[i])*pow(10,n-1-i,2019))%2019


p=-1
for i in range(len(dp)-1):
    if dp[i]==dp[i+1]:
        dp[i]=p
        p=p-1



c=coun.Counter(dp)
sum=0
for v in c.values():
    sum+=v*(v-1)//2

for i in dp:
    if i==0:
        sum+=1

if dp[-1]==0:
    sum=sum-1
print(sum)

Solution (Python):
S=input()

mod=2019
D={}
S=S[::-1]
now=0

for i in range(len(S)):
    if (int(S[i])*pow(10,i,mod)+now)%mod not in D:
        D[(int(S[i])*pow(10,i,mod)+now)%mod]=1
    else:
        D[(int(S[i])*pow(10,i,mod)+now)%mod]+=1
    now=(int(S[i])*pow(10,i,mod)+now)%mod

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

Solution (Python):
S = input()
n = len(S)
dp = {0:1}
q = 1
p = 0
for i in range(n):
    p += int(S[n-1-i])*q
    q *= 10
    q = q % 2019
    p = p % 2019
    if p not in dp:
        dp[p] = 1
    else:
        dp[p] += 1
print(sum(dp[i]*(dp[i]-1)//2 for i in dp))

Solution (Python):
from collections import Counter
S = list(input())
S.reverse()
L = len(S)
dp = [0] * (L+1)
tmp = 0
for i in range(L):
    tmp += int(S[i]) * pow(10, i, 2019)
    tmp %= 2019
    dp[i] = tmp

c = Counter(dp)
ans = 0
for i, v in c.items():
    ans += v * (v-1) // 2

print(ans)

Solution (Python):
s = list(input())
mods = [0]*(len(s))
countRemainder = [0] * 2019
cnt = 0


m = 1
mod = 0
for i in range(len(s)):
    mod += int(s[len(s) - i - 1]) * m

    mod %= 2019
    m *= 10
    m %= 2019

    countRemainder[mod] += 1

countRemainder[0] += 1

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

print(cnt)

Solution (Python):
S=input()
dp = {0:1}

p=0
q=1

for i in range(len(S)-1,-1,-1):
  p += (int(S[i])*q)
  p = p%2019
  q *= 10
  q = q%2019
  if p not in dp:
    dp[p]=0
  dp[p]+=1


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

Solution (Python):
s = list(input())
mods = [0]*(len(s))
countRemainder = [0] * 2019
cnt = 0


m = 1
mod = 0
for i in range(len(s)):
    mod += int(s[len(s) - i - 1]) * m

    mod %= 2019
    m *= 10
    m %= 2019

    countRemainder[mod] += 1

countRemainder[0] += 1

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

print(cnt)

Solution (Python):
S = input()

S = S[::-1]
result = 0
t = [0] * 2019
m = 1
n = 0
for i in range(len(S)):
    t[n] += 1
    n += int(S[i]) * m
    n %= 2019
    result += t[n]
    m *= 10
    m %= 2019
print(result)

Solution (Python):
def main():
    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
        mods[current % 2019] += 1
        x = x * 10 %2019
    
    for i in mods:
        ans += i*(i-1)//2
    print(ans)
if __name__ == '__main__':
    main()

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):
def find(S):
    S = S[::-1]
    number = [0] * 2019
    ans = 0
    cur = 0
    power = 1
    for i in range(len(S)):
        
        cur += power * int(S[i])
        power *= 10
        power %= 2019
        cur %= 2019
        ans += number[cur]
        if cur == 0:
            ans += 1
        number[cur] += 1
        
    return ans

print(find(input()))

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

d = 1
M = []
for s in S:
    M.append(int(s)*d % 2019)
    d *= 10
    d %= 2019

S = [0]
for m in M:
    S.append((S[-1]+m) % 2019)

C = collections.Counter(S)

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

Solution (Python):
S = input()
 

dp = [0]*2019
c = 0
dp[0] = 1

p = 0
q = 1
for i in range(len(S)):
  p += int(S[len(S)-1-i])*q
  p %= 2019
  q *= 10
  q %= 2019
  dp[p] += 1
 
for j in dp:
  c += j * (j-1) // 2
print(c)

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

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

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

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

if __name__ == '__main__':
    main()

Solution (Python):
ss=input().rstrip()

x=1
y=0
mod=[0]*3000
ans=0
mod[0]=1
for i in range(len(ss)):
  s=ss[i*(-1)-1]
  n=int(s)
  y=(y+x*n)%2019
  ans+=mod[y]
  mod[y]+=1
  x=(x*10)%2019
print(ans)

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):
import numpy as np

s = input()

d = [ int( 0 ) ] * 2019
d[ 0 ] = int( 1 )
r = int( 0 )
t = int( 1 )

for si in reversed( s ):


    r = int( si ) * t + r
    r = r % 2019

    t = t * 10
    t = t % 2019

    d[ r ] = d[ r ] + 1

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

print( ans )

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

T=[]
T.append(0)
tmp=""
d=[0 for _ in range(2019)]
d[0]=1
r=0
t=1
for i in range(N):
    s=S[N-1-i]
    r+=int(s)*t
    r%=2019
    t*=10
    t%=2019
    d[r]+=1

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

print(ans)

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







T=[]
T.append(0)
tmp=""
d=[0 for _ in range(2019)]
d[0]=1
r=0
t=1
for i in range(N):
    s=S[N-1-i]
    r+=int(s)*t
    r%=2019
    t*=10
    t%=2019 
    d[r]+=1

ans=0

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

Solution (Python):

def main():
    s = input()
    MOD = 2019
    d = [ 0 for i in range(MOD)]
    
    ans = 0
    k = 0
    d[0] = 1
    s = s[::-1]
    
    p = 1
    for i in s:
        
        
        
        k = (p * int(i) + k) % MOD
        
        
        ans += d[k]
        d[k] += 1
        p = (p * 10) % MOD
    print(ans)
    return

if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter
import sys



S = input()
n = len(S)

M = []
m = 0

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

M.append(0)  

c = Counter(M)

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

print(int(sum))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
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 list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    s = [int(c) for c in S()]
    t = [0] * 2019
    r = 0
    for c in s:
        u = [0] * 2019
        u[c] = 1
        for i in range(2019):
            u[(i*10+c) % 2019] += t[i]
        t = u
        r += t[0]

    return r

print(main())

Solution (Python):







def main():
    s = input()
    MOD = 2019
    d = [ 0 for i in range(MOD)]
    ans = 0
    k = 0
    d[0] = 1
    s = s[::-1]
    p = 1
    for i in s:
        k = (p * int(i) + k) % MOD
        ans += d[k]
        d[k] += 1
        p = (p * 10) % MOD
    print(ans)
    return

if __name__ == "__main__":
    main()

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

for i in range(1, N):
    mod[i] = mod[i - 1] * 10 % 2019
for i in range(N):
    mod[i] *= int(S[i])
cumsum = [0] * N
cumsum[0] = mod[0]
for i in range(1, N):
    cumsum[i] = (cumsum[i - 1] + mod[i]) % 2019
cnt = collections.Counter(cumsum)
ans = cnt[0]
for i in range(2019):
    c = cnt[i]
    ans += c * (c - 1) // 2
print(ans)

Solution (Python):
mod = 2019
s = input()
n = len(s)
w = 0
d = {}
p = 1
for i in reversed(range(n)):
	w += int(s[i]) * p
	p *= 10
	w %= mod
	p %= mod
	if w in d:
		d[w] += 1
	else:
		d[w] = 1
if 0 in d:
	d[0] += 1
else:
	d[0] = 1
o = 0
for x in d:
	o += d[x] * (d[x] - 1) // 2
print(o)

Solution (Python):
mod = 2019
s = input()
n = len(s)
w = 0
d = [0] * mod
p = 1
for i in reversed(range(n)):
	w += int(s[i]) * p
	p *= 10
	p %= mod
	w %= mod
	d[w] += 1
d[0] += 1
o = 0
for x in d:
	o += x * (x - 1) // 2
print(o)

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

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

Solution (Python):
s=input()

counter=[0]*2019
counter[0]=1
num=0
t=1
prefer=0
for i in reversed(s):
    num+=int(i)*t
    num%=2019
    t*=10
    t%=2019
    counter[num]+=1

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

Solution (Python):
from collections import Counter
l = len(S := input())
counts = Counter((n := (n + (d := d * 10 % 2019) * int(S[-i])) % 2019 if i else (n := 0 * (d := 202)) for i in range(l + 1)))
print(sum(n * (n - 1) // 2 for n in counts.values()))

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

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

num, d = 0,1 
'''
charに一桁ずつ取り出す。そのmod2019を考え、累積和をとる。
しかし、それぞれの数字には10の累乗がかかっているので、それについては別途dを用意してmod2019をとる
つまり、numは1桁目のmod2019、2桁目のmod2019に1桁目のmod2019を加える
'''
for char in s:
  num += int(char) * d
  num %= 2019
  d *= 10
  d %= 2019
  counts[num] += 1

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

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

n = len(s)
m = [0]
mod = 0
ten = 1
for i in s[::-1]:
  mod += (int(i)*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):
s=input()
tmpsum=0
ruiseki=[0]
dic={}
so=2019

for i in range(1,len(s)+1):
    tmpsum+=(int(s[-i])*pow(10,i-1,so)) % so
    tmpsum%=so
    ruiseki.append(tmpsum)

for rui in ruiseki:
    if rui in dic:
        dic[rui]=dic[rui]+1
    else:
        dic[rui]=1


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

print(int(output))

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

t=0

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


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

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

print(ans)

Solution (Python):


from collections import Counter

s = input()

count = 0
counter = Counter([0])

suffix = 0
pow = 1
for i in range(len(s) - 1, -1, -1):
    suffix = (int(s[i]) * pow + suffix) % 2019
    pow = pow * 10 % 2019
    count += counter[suffix]
    counter[suffix] += 1

print(count)

Solution (Python):


from collections import Counter

s = input()

count = 0
counter = Counter([0])

suffix = [0] * (len(s) + 1)
pow = 1
for i in range(len(s) - 1, -1, -1):
    suffix[i] = (int(s[i]) * pow + suffix[i + 1]) % 2019
    pow = pow * 10 % 2019
    count += counter[suffix[i]]
    counter[suffix[i]] += 1

print(count)

Solution (Python):
s = input()

n = len(s)
mod_list = [0]*2019
mod_list[0] = 1
t = 0
keisu = 1
for i in range(n):
  t = (int(s[n-1-i])*keisu+t) %2019
  keisu = keisu*10 %2019
  mod_list[t]+= 1
count = 0
for k in range(2019):
  count += mod_list[k] * (mod_list[k]-1)//2
print(count)

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

ans = 0
mods = [0]
s = [int(a) for a in s[::-1]]
x = 0
for i in range(len(s)):
    x += s[i] * pow(10, i, 2019)
    mods.append(x%2019)

mods = Counter(mods)

for k in mods.keys():
    counts = mods[k]
    ans += counts * (counts-1) // 2
print(ans)

Solution (Python):
import collections as col
cnt = col.Counter()
cnt[0] += 1


s = input()
n = len(s)

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

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

print(ans)

Solution (Python):
m=2019;l=[0]*m;a=b=0;k=1
for c in input():l[b%m]+=1;b-=int(c)*k;a+=l[b%m];k=k*202%m
print(a)

Solution (Python):
s = input()
mod = 2019
ls = [1]+[0]*2018
ans = 0
temp=0
m=1
for i in range(len(s)):
    temp= (temp + m*int(s[-i-1]))%mod
    m=(m*10)%mod

    ls[temp] += 1

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

Solution (Python):
s = input()
mod = 2019
ls = [1]+[0]*2018
ans = 0
temp=0
m=1
for i in range(len(s)):
    temp= (temp + m*int(s[-i-1]))%mod
    m=(m*10)%mod

    ls[temp] += 1

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

Solution (Python):
m = 2019
l = [0]*m
a = b = 0;k = 1
for c in input():
  l[b % m] += 1
  b -= int(c)*k
  a += l[b % m]
  k = k*202 % m
print(a)

Solution (Python):

import sys
from collections import Counter


def solve(S: str):
    
    
    
    n = len(S)
    c = [0] * (n + 1)  
    for i in reversed(range(n)):
        c[i] = (c[i + 1] + int(S[i]) * pow(10, n - 1 - i, 2019)) % 2019
    print(sum(v * (v - 1) // 2 for v in Counter(c).values()))



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    S = next(tokens)  
    solve(S)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
d = defaultdict(int)
S=input()
S=S[::-1]
i=0
x=0
MOD=2019
for s in S:
  x+=(int(s)*pow(10,i,MOD))%MOD
  x%=MOD
  d[x]+=1
  i+=1
ans=0
for k in d.values():
  ans=ans+k*(k-1)//2
print(ans+d[0])

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

Solution (Python):
S = input()

from collections import defaultdict
mod = 2019
N = len(S)
D = defaultdict(int)
S = S[::-1]
ans = 0
T = 0
D[0]+=1
for i in range(N):
    s = int(S[i])*pow(10,i,mod)
    T = (T+s)%mod
    ans += D[T]
    D[T]+=1
print(ans)

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

ans = 0
tot = 0
from collections import defaultdict
dic = defaultdict(int)
for i in range(N):
    dic[tot] += 1
    tot += int(rS[i]) * pow(10,i,2019)
    tot %= 2019
    ans += dic[tot]

print(ans)

Solution (Python):
from collections import Counter
def main():
    S=input()
    remainders=[0]
    sub=0
    pow10=1
    for i in range(len(S)-1,-1,-1):
        remainders.append((remainders[-1]+pow10*int(S[i]))%2019)
        pow10=((pow10%2019)*(10%2019))%2019
    d=Counter(remainders)
    ans=0
    for key in d:
        ans+=(d[key]*(d[key]-1))//2
    print(ans)
if __name__=='__main__':
    main()

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

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

ans = 0
from collections import Counter
from math import factorial
c = Counter(cum)
for v in c.values():
    if v >= 2:
        ans += factorial(v) // (factorial(v-2)*2)

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    S = list(map(int, list(input())))
    S = S[::-1]
    n = len(S)
    mod = 2019

    A = [0] * n
    times = 1
    for i in range(n):
        A[i] = S[i] * times % mod
        times = times * 10 % mod

    
    R = [0] * (n + 1)
    for i in range(n):
        R[i+1] = (R[i] + A[i]) % mod
    
    cnt = {}
    ans = 0
    for i in range(n+1):
        r = R[i] % mod
        
        ans = ans + cnt.get(r, 0)
        
        
        cnt[r] = cnt.get(r, 0) + 1
    
    print(ans)

if __name__ == '__main__':
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    S = list(map(int, list(input())))
    S = S[::-1]
    n = len(S)
    mod = 2019

    A = [0] * n
    times = 1
    for i in range(n):
        A[i] = S[i] * times
        times = times * 10 % mod

    
    R = [0] * (n + 1)
    for i in range(n):
        R[i+1] = (R[i] + A[i]) % mod
    
    cnt = {}
    ans = 0
    for i in range(n+1):
        r = R[i] % mod
        
        ans = ans + cnt.get(r, 0)
        
        
        cnt[r] = cnt.get(r, 0) + 1
    
    print(ans)

if __name__ == '__main__':
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1
def II(): return int(input())
 
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
 
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
 
INF = float('inf')
 
def solve():
    S = list(map(int, list(input())))
 
    S = S[::-1]
    
    n = len(S)
    mod = 2019
 
    
    A = [0] * (n)
    a = 1
    for i in range(n):
        A[i] = S[i] * a
        a = a * 10 % mod
    
 
    
    R = [0] * (n+1)
    for j in range(n):
        R[j+1] = (R[j] + A[j]) % mod
    
 
    
    cnt = {}
    ans = 0
    for l in range(0, n+1):
        r = R[l]
        ans = ans + cnt.get(r, 0)
        cnt[r] = cnt.setdefault(r, 0) + 1
    print(ans)
 
if __name__ == '__main__':
    solve()