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):
from collections import Counter
def main():
    S = list(map(int, input()))
    S = S[::-1]
    T = [0] * len(S)
    P = 2019
    T[0] = S[0] % P
    power = 1
    for i in range(1, len(S)):
        power *= 10
        power %= P
        T[i] = T[i-1] + power * S[i]
        T[i] %= P
    counter = Counter(T)
    ans = sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):



def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    
    

    n = input().rstrip()
    n = n[::-1]
    res = [0]*2019
    res[0] += 1
    b = 1
    c = 0
    for i in range(len(n)):
        a = int(n[i])
        c += a*b
        c %= 2019
        res[c] += 1
        b = b*10%2019
    ans = 0
    for i in res:
        if i>=2:
            ans += i*(i-1)//2
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
a = [1] + [0] * 2018
s, p = 0, 1
for c in reversed(input()):
  s = (s + p * int(c)) % 2019
  p = p * 10 % 2019
  a[s] += 1
print(sum(x * (x - 1) // 2 for x in a))

Solution (Python):
from collections import Counter

s = input()
mod1 = 673
mod2 = 3

num1 = 0
num2 = 0
li1 = []
li2 = []
pw1 = 10
pw2 = 10
for i, e in enumerate(s, 1):
    num1 *= 10
    num1 += int(e)
    num1 %= mod1
    inv = pow(pw1, mod1 - 2, mod1)
    li1.append(num1 * inv % mod1)

    num2 *= 10
    num2 += int(e)
    num2 %= mod2
    inv = pow(pw2, mod2 - 2, mod2)
    li2.append(num2 * inv % mod2)

    pw1 *= 10
    pw1 %= mod1
    pw2 *= 10
    pw2 %= mod2

li = [0] + [10 * e1 + e2 for e1, e2 in zip(li1, li2)]
c = Counter(li)

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

print(ans)

Solution (Python):
S=input()
p=2019
h=0
d=1
t=0
c=[0]*p
c[0]=1
for s in reversed(S):
  m=int(s)*d%p
  h=(h+m)%p
  t+=c[h]
  c[h]+=1
  d=d*10%p
print(t)

Solution (Python):





s = list(map(int, list(input())))
n = len(s)
MODULO = 2019

power = 1
prefix_ = [0 for _ in range(n+1)]
for i in range(n-1, -1, -1):
	prefix_[i] = (prefix_[i+1] + power*s[i]) % MODULO
	power *= 10
	power %= MODULO

seen = {}
ans = 0
for item in prefix_:
	ans += seen.get(item, 0)
	seen[item] = seen.get(item, 0) + 1





print(ans)

Solution (Python):
from collections import defaultdict
 
 
def solve2(s):
    ans = 0
    for i, c in enumerate(s):
        if c in '02468':
            ans += i + 1
    return ans
 
 
def solve5(s):
    ans = 0
    for i, c in enumerate(s):
        if c in '05':
            ans += i + 1
    return ans
 
 
def solve_other(s, p):
    reminders = defaultdict(lambda: 0)
    tmp = 0
    mul = 1
    for c in s[::-1]:
        c = int(c)
        tmp = (tmp + c * mul) % p
        mul = mul * 10 % p
        reminders[tmp] += 1
    reminders[0] += 1
    ans = 0
    for r, cnt in reminders.items():
        ans += cnt * (cnt - 1) // 2
    return ans
 
 

s = input()
n = len(s)
p = 2019


if p == 2:
    print(solve2(s))
elif p == 5:
    print(solve5(s))
else:
    print(solve_other(s, p))

Solution (Python):
S = list(str(input()))
S = [int(s) for s in S]
n = len(S)

S.reverse()

def power(a, n, mod):
  bi=str(format(n,"b")) 
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

cum1 = [-1]*(n+1)
cum1[0] = 0
for i in range(n):
    temp = cum1[i]+S[i]*power(10, i, 673)
    cum1[i+1] = temp%673


cum2 = [-1]*(n+1)
cum2[0] = 0
for i in range(n):
    temp = cum2[i]+S[i]*power(10, i, 3)
    cum2[i+1] = temp%3


d = {}
ans = 0
for i in range(n+1):
    c1 = cum1[i]
    c2 = cum2[i]
    if (c1, c2) in d:
        ans += d[(c1, c2)]
        d[(c1, c2)] += 1
    else:
        d[(c1, c2)] = 1
print(ans)

Solution (Python):
import collections
p = 2019
s=input()
n=len(s)
arr=[int(s[i]) for i in range(len(s))] 
if p==2 or p==5: 
 ans=0
 for i in range(n):
   if arr[i]%p==0:
     ans+=i+1
 print(ans)
else: 
 dic=collections.defaultdict(int)
 tmp=0
 for i in range(n-1,-1,-1): 
   tmp+=arr[i]*pow(10,n-1-i,p)
   tmp%=p
   dic[tmp]+=1
 ans=0
 rem=0 
 for i in range(n-1,-1,-1):
   ans+=dic[rem]
   rem+=arr[i]*pow(10,n-1-i,p) 
   rem%=p
   dic[rem]-=1 
 print(ans)

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

Solution (Python):
p = 2019
s = [int(i) for i in input()]
p_cnt = 0
 
s = s[::-1]
div_dic = dict(zip(range(p), [0] * p))
tmp = 0

for i in range(len(s)):
    tmp += s[i] * pow(10, i, p)
    tmp %= p
    div_dic[tmp] += 1

for v in div_dic.values():
    p_cnt += v * (v - 1)
p_cnt //= 2
p_cnt += div_dic.get(0)
 
print(p_cnt)

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

num = [0] * 2019
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % 2019
    _10 *= 10
    _10 %= 2019
    ans += num[now]
    num[now] += 1
print(ans)

Solution (Python):
S = [int(i) for i in input()]

def solve(S):
    n = len(S)
    cum = [0]*(n+1)
    mods = [0]*n
    mods[0] = 1
    for i in range(1,n):
        mods[i] = mods[i-1]*10%2019
    for i in range(n):
        cum[i+1] = (cum[i]+S[n-1-i]*mods[i])%2019
    c = [0]*2019
    for i in range(n+1):
        c[cum[i]] += 1
    ans = 0
    for v in c:
        ans += v*(v-1)//2
    return ans
print(solve(S))

Solution (Python):
S=input()
a=0
b=[0]*2019
No=[None]*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)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
S=list(map(int,input()))
N=len(S)
P=2019
num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + S[i] * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1

print(ans)

Solution (Python):
s = input()
mod = [0] * 2019

cur_mod = 0
ten_mod = 1
mod[0] = 1
for c in s[::-1]:
  cur_mod = (cur_mod + int(c) * ten_mod) % 2019
  ten_mod = (ten_mod * 10) % 2019
  mod[cur_mod] += 1

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

print(count)

Solution (Python):
p = 2019
s = list(map(int, list(input())))[::-1]

sum = 0
cnt = [0] * p
cnt[0] = 1
n = len(s)
for i in range(n):
    d = s[i] * pow(10, i, p)
    sum = (sum + d) % p
    cnt[sum] += 1

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


print(ans)

Solution (Python):
import sys

M = 2019
S = sys.stdin.readline().rstrip()
N = len(S)

dmod = [0] * (N + 1)
amod = [0] * (N + 1)
tenmod = 1
prev_amod = 0
mcnt = [0] * 2019
ans = 0
for i in range(N, -1, -1):
    d = ord(S[i]) - ord("0") if i < N else 0
    dmod[i] = d * tenmod % M
    amod[i] = (dmod[i] + prev_amod) % M
    ans += mcnt[amod[i]]
    mcnt[amod[i]] += 1
    tenmod = tenmod * 10 % M
    prev_amod = amod[i]
print(ans)

Solution (Python):
s = map(int,raw_input())
dp = [0] * 2019
count = 0
for j in range(len(s)):
    ndp = [0] * 2019
    ndp[s[j]] += 1
    for k in range(len(dp)):ndp[(10*k + s[j]) % 2019] += dp[k]
    count += ndp[0]
    dp = ndp

print count

Solution (Python):
import collections
s = map(int,raw_input())

dp = [0] * 2019
count = 0
for j in range(len(s)):
    ndp = [0] * 2019
    ndp[s[j]] += 1
    for k in range(len(dp)):
        ndp[(10*k + s[j]) % 2019] += dp[k]
    count += ndp[0]
    dp = ndp[::]

print count

Solution (Python):

def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

  return (x * K) % mod


MOD = 2019
array = [0] * (MOD+1)

array[0] = 1

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

n = 0
for i in range(len(s)):
  n += int(s[i]) * pow(10,i,MOD)
  n %= MOD
  array[n] += 1
  
ans = 0
for i in range(len(array)):
  if array[i] == 1 or array[i] == 0:
    continue
  
  tmp = array[i] * (array[i]-1) // 2
  ans += tmp
  
print(ans)

Solution (Python):


s = input()
n = len(s) 

rs = [1]*n
for i in range(1,n):
  rs[i] = rs[i-1]*10 %2019
  
ls = [0]*2019
ls[0]+=1

r = 0
for i in range(n-1,-1,-1):
  r += int(s[i]) * (rs[n-i-1])
  r %= 2019
  ls[r] += 1

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

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

mod = 0
count = [0]* P
ten = 1
count[mod] += 1
for i in range(N):
    mod = (mod + int(S[N-i-1]) * ten) % P
    ten = ten * 10 % P
    count[mod] += 1

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

print(res)

Solution (Python):
S = input()
N = len(S)
P = 2019
 
res = 0
mp = [0]*P
mp[0] = 1
cur = 0
p10 = 1
for c in S[::-1]:
    cur = (cur + int(c)*p10) % P
    res += mp[cur]
    mp[cur] += 1
    p10 *= 10
    p10 %= P
 
print(res)

Solution (Python):
a = list(map(int,list(input())))
ans = 0
b = 0
c = [0 for i in range(2019)]
c[0] = 1
for i in range(len(a)):
  b = (b+pow(10,len(a)-i,2019)*a[i])%2019
  c[b] += 1
c = list(map(lambda x:x*(x-1)//2,c))
ans = sum(c)
print(ans)

Solution (Python):
def power_func(a, b, p):
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, p)
        return d * d % p
    if b % 2 == 1:
        return (a * power_func(a, b - 1, p)) % p

S = input()
ansl = [0]*2019
temp = 0
for i in range(len(S)):
    temp = (temp+int(S[-i-1])*power_func(10,i,2019))%2019
    ansl[temp]+=1
ans = (ansl[0]+1)*ansl[0]/2

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

print(int(ans))

Solution (Python):
s = list(input())
n = len(s)
mod = 2019
cnt = [0 for _ in range(mod)]
cnt[0] = 1
r = 0
rs = []
for i in range(n - 1, -1, -1):
    r += int(s[i]) * pow(10, n - 1 - i, mod)
    r %= mod
    cnt[r] += 1
ans = sum([cnt[i] * (cnt[i] - 1) // 2 for i in range(mod)])
print(ans)

Solution (Python):
from collections import Counter
s = input()
n=len(s)
res = [0] * (len(s)+1)
i = 1
res10p = 1
for c in reversed(s):
    res[i] = (res[i-1] + res10p*int(c))%2019
    i = i+1
    res10p = res10p*10%2019

dic = Counter(res)
cnt = 0
for v in dic.values():
    if v >= 2:

        cnt += v * (v-1) // 2
print(cnt)

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

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp



class UnionFindEx:
    def __init__(self, size):
        
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    S = input()
    d = [0]*2019
    dn = [0]*2019
    ans = 0
    for s in S:
        sn = int(s)
        dn[sn] += 1
        for i in range(2019):
            dn[(i*10+sn)%2019] += d[i]
        d, dn = dn, d
        for i in range(2019):
            dn[i] = 0
        ans += d[0]
    print(ans)






main()

Solution (Python):
k=2019
s=map(int,list(input()))
ans=0

inv10=202
inv=10
total=0
S=[0]*k
S[0]=1
for i,p in enumerate(s):
    inv*=inv10
    inv%=k
    total+=p*inv
    total%=k
    ans+=S[total]
    S[total]+=1
"""
for i,s in enumerate(S):
    if s>0:
        print(i,s)
"""
print(ans)

Solution (Python):
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

S = input()
N = len(S)
q = deque(S)

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

S = S[::-1]
m = [0]
for i in range(N):
    c = int(S[i])
    n = (c * mod10[i] + m[i]) % 2019
    m.append(n)


modCnt = [0] * 2020

for num in m:
    modCnt[num] += 1

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

print(ans)

Solution (Python):
s=input()
n=len(s)
mod=[0]*(n+1)
s=s[::-1]
for i in range(n):
	mod[i+1]=(mod[i]+pow(10,i,2019)*int(s[i])%2019)%2019
mod.sort()
cnt=1
ans=0
for i in range(n):
	if mod[i]==mod[i+1]:
		cnt+=1
	else:
		ans+=cnt*(cnt-1)//2
		cnt=1
ans+=cnt*(cnt-1)//2
print(ans)

Solution (Python):
import math
s = input()
ls = [(ord(s[len(s) - i - 1]) - ord('0')) for i in range(len(s))]
cnt = [0 for _ in range(2019)]
cur = 0
ans = 0
power = 1
cnt[0] = 1
for i in ls:
    cur = (cur + power * i) % 2019
    ans = ans + cnt[cur]
    cnt[cur] = cnt[cur] + 1
    power = (power * 10) % 2019

print(ans)

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

for i in range(len(S)):
    S[i] = int(S[i])

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

from collections import  Counter

c = Counter(A)

ans = c[0]

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

print(ans)

Solution (Python):
import sys, copy, math, heapq, bisect
from itertools import accumulate
from collections import deque, defaultdict, Counter
sys.setrecursionlimit(500000)

S = list(input())[::-1]
N = len(S)
D = [1]
for i in range(N):
    D.append(D[-1]*10%2019)
M = [(int(S[i])*D[i])%2019 for i in range(N)]
SS = [M[0]]
for i in range(1,N):
    SS.append((SS[-1]+M[i])%2019)
count = [0]*2019
for i in range(N):
    count[SS[i]] += 1

ans = 0
for c in range(len(count)):
    if c==0:
        ans += count[c]
    ans += (count[c] * (count[c] - 1)) // 2

print(ans)

Solution (Python):
import collections

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

C = collections.Counter(S)
ans = 0
for x in C.keys():
    if x == 0:
        ans += C[0] + C[0] * (C[0] - 1) // 2
    else:
        ans += C[x] * (C[x] - 1) // 2
print(ans)

Solution (Python):
def modpow(d, b, p, mod=2019):
    ret = 1
    while p > 0:
        if p % 2 == 1:
            ret = ret * b % mod
        b = b * b % mod
        p //= 2
    return (d * ret) % mod


S = input()
C = [0]
for i in range(len(S)):
    C.append((C[-1] + modpow(int(S[-(i + 1)]), 10, i)) % 2019)
Cd = {}
for c in C[1:]:
    Cd[c] = Cd.get(c, 0) + 1
print(Cd.get(0, 0) + sum([v * (v - 1) // 2 for v in Cd.values()]))

Solution (Python):
S = list(map(int, input()))
n = len(S)
S = S[::-1]

Smod = [S[i] * pow(10, i, 2019) %2019 for i in range(n)]
Scum = [0]*n
Scum[0] = Smod[0]


for i in range(1, n):
  Scum[i] = (Scum[i-1] + Smod[i])%2019

from collections import Counter
c = Counter(Scum)

ans = 0
for k in c:
  if k!=0 or k==0:
    ans += c[k]*(c[k] - 1)//2
    
    
for i in range(n):
  if Scum[i]==0:
    ans += 1
    
    
print(ans)

Solution (Python):
MOD=2019

S=list(int(s) for s in input()[::-1])
T=[S[0]]
for i in range(1,len(S)):
    T.append(T[-1]+S[i]*pow(10,i,MOD))
cnt={}
for i in range(2019):
    cnt[i]=0
for t in T:
    cnt[t%MOD]+=1
ans=0
for i in range(2019):
    c=cnt[i]
    if c>=2:
        ans+=c*(c-1)//2
ans+=cnt[0]
print(ans)

Solution (Python):

import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))

def resolve():
    S=input()
    n=len(S)
    
    S2=[0]*n
    digit=0
    for i in range(n-1,-1,-1):
        s=int(S[i])
        S2[i]=(s*pow(10,digit,2019))%2019
        digit+=1
    

    S3=[0]*n;subsum=0
    for j,s2 in enumerate(S2):
        subsum+=s2;subsum%=2019;S3[j]=subsum
    S3.append(0)
    

    from collections import Counter
    c=Counter(S3).values()
    ans=0
    for k in c:
        if k>1:
            ans+=(k*(k-1))//2
    print(ans)

resolve()

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

S = list(input())
S = list(map(int, S))
s = [0] * len(S)
mod = 2019
s[-1] = S[-1]
d = 1
for i in range(len(s) - 2, -1, -1):
    d = (d * 10) % mod
    s[i] = (S[i] * d) % mod

acc = list(accumulate(s[::-1]))[::-1] + [0]
acc = [i % mod for i in acc]
answer = sum(i * (i - 1) // 2 for i in Counter(acc).values())
print(answer)

Solution (Python):
S_str=str(input())
S=int(S_str[-1])
N=len(S_str)

mod=[0]*2019
mod[0]=1
now=S%2019
mod[now]+=1

for i in range(N-1)[::-1]:
    
    next=pow(10,N-1-i,2019)
    next=(next*int(S_str[i]))%2019
    now=(now+next)%2019
    mod[now]+=1

    

def culc(x):
    return x*(x-1)//2


ans=0
for j in range(len(mod)):
    ans+=culc(mod[j])

print(ans)

Solution (Python):
from collections import defaultdict

S = input()
N = len(S)
MOD = 2019

rems = [0] * N
rems[-1] = int(S[-1]) % MOD
last = int(S[-1])
tens = 1
for i in range(N - 1):
    tens = tens * 10 % MOD
    last = int(S[N - 2 - i]) * tens + last
    rems[N - 2 - i] = last % MOD
pos = defaultdict(int)
for i in range(N):
    r = rems[i]
    pos[r] += 1
ans = pos[0]
for i in range(MOD):
    ans += pos[i] * (pos[i] - 1) // 2
print(ans)

Solution (Python):

import sys
sysread = sys.stdin.readline
def run():
    S = input()
    mods = [[] for _ in range(2019)]
    mods[0].append(0)

    tmp = 0
    tmp10 = 1
    for i in range(1, len(S)+1):
        if i == 1:
            tmp10 = 1
        else:
            tmp10 = (tmp10 * 10) % 2019
        tmp = (tmp10* int(S[-i]) + tmp)% 2019
        mods[tmp].append(i)

    count = 0
    for ns in mods:
        l = len(ns)
        count += l * (l-1) // 2
    print(count)

if __name__ == "__main__":
    run()

Solution (Python):
def pow_with_mod(x, n, m):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
            K %= m
        x *= x
        x %= m
        n //= 2

    return (K * x) % m

def main():
    import sys
    S=sys.stdin.readline().strip()
    N=len(S)
    L=[0]*2019
    now=0
    for i in range(N):
        now+=int(S[-i-1])*pow_with_mod(10, i, 2019)
        now%=2019
        L[now]+=1  
    print(L[0]+sum([x*(x-1)//2 for x in L]))
main()

Solution (Python):
S = input()
l = len(S)
d = {}

m = 0

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

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

Solution (Python):
p = 2019
s = list(map(int, list(input())))[::-1]
n = len(str(s))

sum = 0
cnt = [0] * p
cnt[0] = 1
n = len(s)
for i in range(n):
    d = s[i] * pow(10, i, p)
    sum = (sum + d) % p
    cnt[sum] += 1

ans = 0
if p in [2, 5]:
    if p == 2:
        ok_list = [0, 2, 4, 6, 8]
    if p == 5:
        ok_list = [0, 5]

    for i in range(n):
        d = s[i]
        if d in ok_list:
            ans += n - i
           
else:
    for i in range(p):
        ans += cnt[i] * (cnt[i]-1) // 2


print(ans)

Solution (Python):
R = [0]*2019
s = input()

res = 0
for d in map(int, s):
    new = [0]*2019
    for i in range(2019):
        new[(i*10 + d)%2019] += R[i]
    new[d] += 1
    res += new[0]
    R = new
print(res)

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import defaultdict

s = ns()
n = len(s)
m = 1
c = [0] * (n + 1)

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

ans = 0
dic = defaultdict(int)
for i in range(n, -1, -1):
    ans += dic[c[i]]
    dic[c[i]] += 1

print(ans)

Solution (Python):
S=list(input())
S.reverse()
N=len(S)
R=[0]*N
R10=[0]*N
m=2019
K=0

R10[0]=1
R[0]=int(S[0])%m
for i in range(1,N):
    R10[i]=(R10[i-1]*10)%m
    R[i]=(R[i-1]+int(S[i])*R10[i])%m
d={}
for i in range(2019):
    d[i]=0

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

Solution (Python):
p = 2019
s = list(map(int, list(input())))[::-1]
n = len(str(s))

sum = 0
cnt = [0] * p
cnt[0] = 1
n = len(s)
for i in range(n):
    d = s[i] * pow(10, i, p)
    sum = (sum + d) % p
    cnt[sum] += 1

ans = 0
if p in [2, 5]:
    if p == 2:
        ok_list = [0, 2, 4, 6, 8]
    if p == 5:
        ok_list = [0, 5]

    for i in range(n):
        d = s[i]
        if d in ok_list:
            ans += n - i
           
else:
    for i in range(p):
        ans += cnt[i] * (cnt[i]-1) // 2


print(ans)

Solution (Python):
from collections import Counter
mods = Counter([(0, 0)])
ten_i_mod3 = 1
temp3 = 0
ten_i_mod673 = 1
temp673 = 0
for digit in reversed(input()):
    digit = int(digit)
    temp3 += digit * ten_i_mod3
    temp673 += digit * ten_i_mod673
    temp3 %= 3
    temp673 %= 673
    mods[(temp3, temp673)] += 1
    ten_i_mod3 *= 10
    ten_i_mod673 *= 10
    ten_i_mod3 %= 3
    ten_i_mod673 %= 673
ans = 0
for key in mods:
    n = mods[key]
    ans += n * (n - 1) // 2
print(ans)

Solution (Python):
s=input()

l=[1]

for i in range(2018):
    l.append(0)

ss=0
for i in range(len(s)):
    ss=(int(s[len(s)-i-1])*pow(10,i,2019)+ss)%2019
    l[ss]+=1
n=0
for i in range(2019):
    n+=l[i]*(l[i]-1)//2

print(int(n))

Solution (Python):
from collections import Counter


S = input()
N = len(S)

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

C = Counter(L)
cnt = 0
for key in list(C.keys()):
    k = C[key]
    cnt += (k * (k - 1)) // 2

print(cnt)

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

answer=0
mod_table=[0]*P
mod_table[0]=1
revS=S[::-1]
  
modp=0
mod10=1
for i in range(len(S)):
  mod10=(mod10*10)%P
  
  modp=(modp+mod10*int(revS[i]))%P
  mod_table[modp]+=1
    

for i in range(P):
  answer+=mod_table[i]*(mod_table[i]-1)//2
  
print(answer)

Solution (Python):
S = input()
mod = [0] * 2019
res = 0
for c in S:
    m = int(c)
    new_mod = [0] * 2019
    for i, n in enumerate(mod):
        new_mod[(i*10 + m) % 2019] = n
    new_mod[m] += 1
    mod = new_mod
    res += mod[0]
print(res)

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

MOD = 2019
S.reverse()
cnt = 1
temp = 0
ans = [0]*2019
for i in S:
    temp += int(i)*cnt % MOD
    temp %= MOD
    ans[temp] += 1
    cnt *= 10
    cnt %= MOD

ans[0] += 1

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

Solution (Python):
def d_multiple_of_2019():
    from collections import Counter
    S = [int(ch) for ch in input()]

    s = S[::-1]
    n = len(S)
    u = [0] * n

    
    
    
    
    

    p = 2019
    u[0] = s[0] % p
    power = 1
    for i in range(1, n):
        power *= 10
        power %= p
        u[i] = u[i - 1] + power * s[i]
        u[i] %= p
    count = Counter(u)
    ans = 0
    for k, v in count.items():
        ans += v * (v - 1) // 2
    return ans + count[0]

print(d_multiple_of_2019())

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


def combi(x):
    return (x*(x-1))//2

L=[0]
for i in range(lens):
    L.append((L[-1]+int(s[lens-1-i])*pow(10,i,2019))%2019)

D={i:0 for i in range(2019)}
for ele in L:
    D[ele]+=1

ans=0
for key in D:
    if D[key]>1:
        ans+=combi(D[key])
    
print(ans)

Solution (Python):
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().strip()


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

    
    base = [0] * l
    base[0] = 1
    for i in range(1, l):
        base[i] = (base[i - 1] * 10) % 2019 

    d = defaultdict(int)
    
    pre = 0
    for i in range(l):
        j = l - i - 1
        rem = (pre + int(S[j]) * base[i]) % 2019 
        d[rem] += 1
        
        pre = rem
    
    
    ans = 0
    for rem in d:
        n = d[rem]
        ans += n * (n - 1) // 2
    print(ans + d[0])

    
    
    

if __name__ == "__main__":
    main()

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

for i in range(n):
    
    if accum[i] not in d:
        if accum[i]==0:
            ans+=1
        d[accum[i]]=1
    else:
        if accum[i]==0:
            ans+=1
        ans+=d[accum[i]]
        d[accum[i]]+=1
print(ans)

Solution (Python):
s = input()
mods = [0]*2019
mods[0] = 1
accu = 0
for i, j in enumerate(reversed(s)):
    accu += int(j)*pow(10, i, 2019)
    accu %= 2019
    mods[accu] += 1
ans = 0
for i in mods:
    ans += i*(i-1)//2
print(ans)

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

s = input()
s = list(s)[::-1]
ten = [1]
for _ in range(len(s)):
  ten.append(ten[-1]*10 % 2019)
  
A = [(int(s[i])  * ten[i])%2019 for i in range(len(s))]
A = list(accumulate(A))
A = [a%2019 for a in A]
A = [0] + A

A = Counter(A).most_common()
ans = 0
for _, count in A:
  if count == 1:
    break
  ans += count*(count-1)//2
print(ans)

Solution (Python):
from collections import Counter

M = 2019

Ss = input().rstrip()

As = [0]
A = 0
d = 1
for S in reversed(Ss):
    A += int(S) * d
    A %= M
    As.append(A)
    d = (d*10) % M

As.reverse()


cnt = Counter(As)

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

print(ans)

Solution (Python):
s = input()

tens = 1
mod = 2019

rests = [0 for i in range(len(s))]

for i in range(len(s)):
    if i == 0:
        rests[-(i+1)] = int(s[-(i+1)])
    else:
        rests[-(i+1)] = (rests[-i] + (tens * int(s[-(i+1)]))) % mod

    tens *= 10
    tens = tens % mod

dic = {}
for i in range(len(rests)):
    if dic.get(rests[i], None) is None:
        dic[rests[i]] = 1
    else:
        dic[rests[i]] += 1

ans = 0

for k in dic:
    if k == 0:
        ans += dic[k]
        ans += dic[k] * (dic[k] - 1) // 2

    elif dic[k] > 1:
        ans += (dic[k] * (dic[k] - 1)) // 2

print(ans)

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

Solution (Python):

import sys
from collections import defaultdict
from operator import mul
from functools import reduce


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def solve(S: str):
    if len(S) < 4:
        print(0)
        exit()
    prev = int(S[-1])
    digit = 10
    count = defaultdict(int)
    for i in range(1,len(S)+1):
        k = prev % 2019
        
        count[k]+=1
        if i == len(S):
            break
        prev = (prev + digit*int(S[-i-1]))%2019
        digit=digit*10%2019
    sum = 0
    for k in count:
        if k == 0:
            sum += count[k]
            if count[k] >= 2:
                sum += combinations_count(count[k], 2)
            continue
        if count[k] < 2:
            continue
        sum += combinations_count(count[k],2)
    print(sum)
    return



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 itertools import accumulate
from collections import Counter

mod = 2019
s = input()
keta = len(list(s))
JJ = [0 for i in range(keta + 2)]
JJ[0] = 1
JJG = [0 for i in range(keta + 2)]
JJG[0] = 1
for i in range(1, keta + 2):
    JJ[i] = (10 * JJ[i - 1]) % mod
    JJG[i] = pow(JJ[i], mod - 2, mod)

S = [0] * (keta)


for i in range(keta - 1, -1, -1):

    S[i] = int(s[keta - 1 - i]) * JJ[i]
    S[i] %= mod

SA = [0] * (keta)
SA[0] = S[0]
for i in range(keta - 1):
    SA[i + 1] = SA[i] + S[i + 1]
    SA[i + 1] %= mod


ans = 0

SC = Counter(SA)
for e, i in Counter(SA).items():
    if e > 0:
        ans += i * (i - 1) // 2
    else:
        ans += i
        ans += i * (i - 1) // 2

print(ans)

Solution (Python):
S = input()

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


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

print(ans)

Solution (Python):

from collections import defaultdict

def submit():
    s = [int(c) for c in input()]
    modp = 2019

    curr = 0
    modp_count = defaultdict(int)
    modp_count[0] = 1
    ans = 0
    base = 1
    for c in reversed(s):
        curr += base * c
        curr_mod = curr % modp
        ans += modp_count[curr_mod]
        modp_count[curr_mod] += 1
        base *= 10
        base %= modp
    
    print(ans)
    

submit()

Solution (Python):
def modpow(d, b, p, mod=2019):
    ret = 1
    while p > 0:
        if p % 2 == 1:
            ret = ret * b % mod
        b = b * b % mod
        p //= 2
    return (d * ret) % mod


S = input()
C = [0]
for i in range(len(S)):
    C.append((C[-1] + modpow(int(S[-(i + 1)]), 10, i)) % 2019)
Cd, C0 = {}, 0
for c in C[1:]:
    if c == 0:
        C0 += 1
    else:
        Cd[c] = Cd.get(c, 0) + 1
print(C0 + C0 * (max(0, C0 - 1)) // 2
      + sum([v * (v - 1) // 2 for v in Cd.values()]))