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()
p=2019;n=len(s)
digit_rm = [0 for _ in range(n)]
for i in range(n):
	digit_rm[i] = (int(s[n-1-i]) * pow(10, i, p) ) % p

remain = [0 for _ in range(n)]
for i in range(n):
	if i == 0:
		remain[i] = digit_rm[i]
	else:
		remain[i] = (remain[i-1] + digit_rm[i]) % p
pcnt = [0 for _ in range(p)]
for i in remain:
	pcnt[i] += 1
ans = pcnt[0]
for num in pcnt:
	if num != 0:
		ans += num * (num - 1) // 2
print(ans)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 2019
mans = inf ;ans = 0 ;count = 0 ;pro = 1

S = list(map(int,input()))
n = len(S)
now10 = 1
for i in range(n-1,-1,-1):
  S[i] = S[i] * now10 % mod
  now10 = now10 * 10 % mod
A = [0]* (n+1)
for i in range(n):
  A[i+1] = (A[i] + S[i]) % mod
C = collections.Counter(A)
for k,e in C.items():
  ans += (e-1)*e//2
print(ans)

Solution (Python):
from collections import Counter

S = input()
MOD = 2019
redisuals = [0]


for i in range(len(S)):
    s = int(S[-i - 1])
    redisuals.append((redisuals[-1] + s * pow(10, i, MOD)) % MOD)

c = Counter(redisuals)

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

ans //= 2
print(ans)

Solution (Python):

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

c = 0
mm = {}
r = 0
mten = 1
for i in range(n - 1, -1, -1):
    ch = int(s[i])
    r = (r + ch * mten) % p
    mten = (mten * 10) % p
    if r in mm:
        c += mm[r]
        mm[r] += 1
    else:
        mm[r] = 1
    if r == 0:
        c += 1

print(c)

Solution (Python):
from collections import defaultdict
def main():
    S = list(map(int,list(input())))
    N = len(S)
    M = [0] * (N + 1)
    ten = 1
    for i in range(N-1,-1,-1):
        M[i] = (S[i] * ten + M[i+1]) % 2019
        ten *= 10
        ten %= 2019

    d = defaultdict(int)

    for m in M:
        d[m] += 1
    ans = 0
    for i, j in d.items():
        ans += j * (j - 1) // 2
    
    print(ans)


if __name__ == "__main__":
    main()

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):
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = list(input())
L = len(S)

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

ans = 0
for i in range(2019):
    m = md[i]

    if m == 0:
        continue

    ans += m * (m - 1) // 2

print(ans)

Solution (Python):
from collections import Counter

S = input()
S = S[::-1]
U = [0] * len(S)

a = 1
for k,v in enumerate(S):
    U[k] = U[k-1] + a * int(v)
    U[k] %= 2019
    a *= 10
    a %= 2019

U.append(0)

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

print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)





S = list(inputS())
N = len(S)

r = []
for i in range(N)[::-1]:
  n = int(S[i])
  if r == []:
    r.append(n)
  else:
    r.append((r[-1]+n*pow(10,N-i-1,2019))%2019)

import collections

c = collections.Counter(r)

res = 0
for i in c.items():
  res += i[1]*(i[1]-1)/2
  if i[0]==0:
    res += i[1]

print(int(res))

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(S: str):
    N = len(S)
    U = [0]*(N+1)
    a = 0
    beki = 1
    for i in range(N-1, -1, -1):
        a += beki*(ord(S[i])-ord("0"))
        a %= 2019
        beki = (beki*10) % 2019
        U[i] = a
    table = [0]*2019

    tot = 0
    for i in range(N-1, -1, -1):
        tot += table[U[i]]
        table[U[i]] += 1
    tot += table[0]
    print(tot)
    return


def main():

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            index=0
            a,b,c=(list(ls[i])+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True








class SegTree:

    def __init__(self,n,init_ls=None,init_val=0,function=lambda a,b:a+b,ide=0):
        self.n=n
        self.ide_ele=ide_ele=ide
        self.num=num=2**(n-1).bit_length()
        self.seg=seg=[self.ide_ele]*2*self.num
        self.lazy=lazy=[self.ide_ele]*2*self.num
        self.segfun=segfun=function
        
        if init_ls==None:
            for i in range(n):
                self.seg[i+self.num-1]=init_val
        else:
            for i in range(n):
                self.seg[i+self.num-1]=init_ls[i]
        
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.segfun(self.seg[2*i+1],self.seg[2*i+2])
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfun(self.seg[k*2+1],self.seg[k*2+2])
        
    def evaluate(k,l,r): 
        if lazy[k]!=0:
            node[k]+=lazy[k]
            if(r-l>1):
                lazy[2*k+1]+=lazy[k]//2
                lazy[2*k+2]+=lazy[k]//2

        lazy[k]=0
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res
    
    def find_min_index(self,p,q,m):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p >>= 1
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res


    def __str__(self):
        
        rt=self.seg[self.num-1:self.num-1+self.n]
        return str(rt)

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)

def dijkstra(edge,st):
    
    
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    
    
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev


ans=0

s=input()
n=len(s)

a=[0]
t=0
m=2019
d=0
for i in s[::-1]:
    t=t+int(i)*pow(10,d,m)
    t%=m
    d+=1
    a.append(t%m)




c=Counter(a)


for i,j in c.items():
    ans+=j*(j-1)//2


print(ans)

Solution (Python):
import math

M = 2019

S = input().strip()

data = []
l = len(S)
d = 1
for i in range(l):
	data.append((d * int(S[l - i - 1]) % M))
	d = (d * 10 % M)

table = [0] * M
table[0] = 1

count = 0
n = 0
for rem in data:
	n = (n + rem) % M
	count += table[n]
	table[n] += 1

print(count)

Solution (Python):
def main():
    S = input()
    p = 2019
    d = {i:0 for i in range(p)}
    d[0] = 1
    r = 0
    x = 0
    for i in range(len(S)):
        x += int(S[len(S)-1-i]) * pow(10, i, p)
        x %= p
        r += d[x]
        d[x] += 1
    return r
print(main())

Solution (Python):


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

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

Solution (Python):
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

NN = 202020
MOD = 10**9+7

INF = float("inf")

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


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

print(ans)

Solution (Python):
from collections import Counter

S = input()

x = [0]
dec = 1
for s in S[::-1] :
  x.append((x[-1] + dec * int(s)) % 2019)
  dec *= 10
  dec %= 2019

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline
import collections


def main():
    S = input().strip()


    N = len(S)
    P = 2019
    M = [0] * N
    for i, s in enumerate(S[::-1]):
        M[i] = (int(s) * pow(10, i, P)) % P

    MA = []
    MA.append(M[0])
    c = collections.Counter()
    ans = 0
    c[0] += 1
    ans += c[MA[0]]
    c[M[0]] += 1
    for i in range(1, N):
        MA.append((MA[i - 1] + M[i]) % P)
        ans += c[MA[i]]
        c[MA[i]] += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
input = sys.stdin.readline


s = [int(item) for item in list(input().rstrip())]
s.reverse()

mod2019 = []
base = 1
for item in s:
    mod2019.append(base * item % 2019)
    base = base * 10 % 2019

cumsum = [0]
for item in mod2019:
    cumsum.append((cumsum[-1] + item) % 2019)

count = [0] * 2020
for item in cumsum:
    count[item] += 1
ans = 0
for cnt in count:
    ans += cnt * (cnt - 1) // 2
print(ans)

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

a = 0
from collections import defaultdict
d = defaultdict(int)
d[0]+=1
for i,s_r in enumerate(S_rev):
    x = pow(10,i,2019)
    
    a = (a+int(s_r)*x)%2019
    
    d[a] += 1


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

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    S = list(input().strip("\n"))
    N = len(S)
    mod = 2019
    D = [0] * (N + 1)
    D[N] = 0
    D[N-1] = int(S[N-1])
    modType = dict()
    modType[D[N-1]] = 1
    modType[0] = 1
    ans = 0
    for i in reversed(range(N - 1)):
        D[i] = (D[i + 1] + int(S[i]) * pow(10, N - i - 1, mod)) % mod
        if D[i] in modType:          
            ans += modType[D[i]]   
            modType[D[i]] += 1
        else:
            modType[D[i]] = 1
    print(ans)
    
    
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
S = input()
pow10 = [1] * len(S)
for i in range(1,len(S)):
    pow10[i] = (pow10[i-1] * 10) % 2019

smod = [0] * (len(S) + 1)
count = [0] * 2019
for i in range(len(S)):
    smod[i+1] = (smod[i] + int(S[-i-1]) * pow10[i]) % 2019
for i in range(len(S) + 1):
    count[smod[i]] += 1

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

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

data = [0]*2019
pre = 0
for i in range(len(S)):
    x = pow(10,i,2019)
    x *= S[-i-1]
    x %= 2019
    data[(pre+x)%2019] += 1
    pre += x


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

print(ans)

Solution (Python):

s = list(input())
N = len(s)
P = 2019
S = [0]*N

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

count = 0

if P != 2 and P != 5:
    now = 0
    remainder = []
    for i in range(1,N+1):
        now += S[N-i] * (pow(10,(i-1),P) )
        remainder.append(now % P)

    result={}
    for i in range (0,len(remainder)):
        item = remainder[i]
        if item in result:
            result[item] = result[item]+1
        else:
            result[item] = 1

    for k in result.keys():
        if k == 0:
            if result[0] >= 2:
                count += result[0] + result[0]*(result[0]-1)//2
            else:
                count += result[0]
        else:
            count += result[k]*(result[k]-1)//2

print(count)

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

Solution (Python):
a = input()
n = len(a)
s = [[0, 0] for i in range(n+1)]
MOD1 = 3
MOD2 = 673
u = [[0 for i in range(MOD2)] for j in range(MOD1)]
ret = 0
c1 = pow(10, MOD1-2, MOD1)
c2 = pow(10, MOD2-2, MOD2)
for i in range(n):
    s[i+1] = [(s[i][0]*10+int(a[i]))%MOD1, (s[i][1]*10+int(a[i]))%MOD2]
    x, y = s[i][0]*pow(c1, i, MOD1)%MOD1, s[i][1]*pow(c2, i, MOD2)%MOD2
    u[x][y] += 1
    x, y = s[i+1][0]*pow(c1, i+1, MOD1)%MOD1, s[i+1][1]*pow(c2, i+1, MOD2)%MOD2
    ret += u[x][y]
print(ret)

Solution (Python):
S=list(input())
N=len(S)
ls=[0 for _ in range(N)]
mod=[0 for _ in range(2019)]
d=10
ls[0]=int(S[-1])
mod[ls[0]]+=1
for i in range(1,N):
  ls[i]=(ls[i-1]+d*int(S[-1-i]))%2019
  d=(d*10)%2019
  mod[ls[i]]+=1


ans=mod[0]
for i in range(N):
  m=ls[i]
  mod[ls[i]]-=1
  ans+=mod[ls[i]]
print(ans)

Solution (Python):
def equalfind(A):
    A.sort()
    s=1
    count=0
    if len(A)==1:
        return count
    else:
        for i in range(0,len(A)-1):
            if A[i]==A[i+1]:
                s+=1
            else:
                count+=s*(s-1)//2
                s=1
        return count+s*(s-1)//2

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

for i in range(1,N):
    data[i]+=data[i-1]
    data[i]%=mod

data=[0]+data
data.sort()
print(equalfind(data))

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


L = 2019
S = input().rstrip()


A = {0 : 1}
ans = 0
tmp = 0
c = 1
for s in S[::-1]:
    n = int(s)
    tmp = (tmp + c*n) % L
    c = c * 10 % L
    if tmp in A:
        A[tmp] += 1
    else:
        A[tmp] = 1

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

Solution (Python):
S = input()
N = len(str(S))
P = 2019
list_a = [0] * P
list_a[0] += 1
counter = 0
temp = 0
power = 1
for i in range(N):
    temp += pow(10, i, P) * int(S[N - i - 1])
    temp %= P
    counter += list_a[temp]
    list_a[temp] += 1
print(counter)

Solution (Python):
import sys
from collections import defaultdict


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

a = []
t = 1
for i in range(n-1, -1, -1):
    a.append((ord(s[i])-ord("0")) * t % p)
    t = t * 10 % p
cum = [0]
for v in a:
    cum.append((cum[-1] + v) % p)

dic = defaultdict(int)
ans = 0
for v in cum:
    ans += dic[v]
    dic[v] += 1
print(ans)

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    s = input()

    power = 1
    dic = [0] * 2019
    dic[0] = 1
    x = 0
    dic1 = {i:j for i,j in zip('0123456789',range(10))}
    for i in range(len(s)-1,-1,-1):
        x += power * dic1[s[i]]
        x %= 2019
        dic[x] += 1
        power *= 10
        power %= 2019
    
    ans = 0
    for v in dic:
        ans += v*(v - 1)//2
    print(ans)
if __name__ == '__main__':
    main()

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

MOD = 2019
rs = [1]
for i in range(N):
    rs.append((10*rs[-1]) % MOD)

res = [0]
for i in range(N):
    s = S[-i-1]
    res.append((res[-1] + s * rs[i]) % MOD)

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

Solution (Python):
S=input()
N=len(S)
A=[0]
for i in range(N):
    s=int(S[-1-i])
    A.append((A[-1]+(s*pow(10,i,2019)))%2019)
d={}
for i in range(len(A)):
    if not A[i] in d:
        d[A[i]]=1
    else:
        d[A[i]]+=1
ans=0
for k in d.keys():
    ans+=d[k]*(d[k]-1)//2
print(ans)

Solution (Python):

import sys


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

A = [0]*(N+1)
R = [0]*(2030)

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

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

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

L = []
N = len(S)
t = 0
k = 1
for i in range(N - 1, -1, -1):
    t = (t + int(S[i]) * k) % MOD
    L.append(t)
    k *= 10
    k %= MOD
R = [0 for _ in range(2019)]
R[0] = 1
for l in L:
    R[l] += 1
res = 0
for r in R:
    res += (r * (r - 1)) // 2
print(res)

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):
from itertools import accumulate,chain
from collections import Counter

MOD = 2019

S = input()

memo = [None]*len(S)
x = 1
for i,c in enumerate(reversed(S)):
    memo[i] = x*int(c)%MOD
    x = (10*x)%MOD

acc = tuple(chain((0,), accumulate(memo, lambda x,y: (x+y)%MOD)))

print(sum(c*(c-1)//2 for c in Counter(acc).values()))

Solution (Python):
s = input()
seen = dict()
seen[0] = 1
curr = 0
mult = 1
out = 0
for c in s[::-1]:
    curr += int(c) * mult
    curr %= 2019
    mult *= 10
    mult %= 2019
    if curr not in seen:
        seen[curr] = 0
    out += seen[curr]
    seen[curr] += 1
print(out)

Solution (Python):
S = input()
n = len(S)
*S, = map(int, S[::-1])
R = [0]*2019

p = 0
for i, s in enumerate(S):
    q = 10**(i % 224) % 2019
    p += s*q
    p %= 2019
    R[p] += 1

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

print(ans)

Solution (Python):
s = str(input())
n = len(s)
x = [0]*2019
x[0] = 1
m = 0
j = 1
for i in range(n):
  m = (m + int(s[-i-1])*j)%2019
  x[m] += 1
  j = (j*10)%2019
ans = 0
for i in range(2019):
  ans += (x[i]*(x[i]-1))//2
print(ans)

Solution (Python):
s=list(input())
s=s[::-1]
for i in range(len(s)):
    s[i]=int(s[i])
data=[0]
x=0
for i in range(len(s)):
    x=pow(10,i,2019)*s[i]+x
    x=x%2019
    data.append(x)
from collections import Counter
data=dict(Counter(data))
ans=0
for key in data.values():
    ans+=(key)*(key-1)//2
print(ans)

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

sum_of_digits = 0

cnts = [0] * 2019

cnts[0] = 1

d = 1

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

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

print(ans)

Solution (Python):
n = input()
l = len(n)
a = [0 for _ in range(2019)]
a[0] = 1
now = 0
ten = [1]
for i in range(l-1):
  ten.append(ten[-1]*10%2019)
ten.reverse()
for i in range(l)[::-1]:
  now += ten[i]*int(n[i])
  now %= 2019
  a[now] += 1
  
ans = 0
for d in range(2019):
  ans += a[d] * (a[d]-1) // 2
print(ans)

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

temp = [1]
for i in range(len(s) - 1):
    temp.append(temp[-1] * 10 % mod)
temp.reverse()
temp2 = []
for i in range(len(s)):
    temp2.append(int(s[i]) * temp[i])
temp3 = [0]
for i in range(len(s)):
    temp3.append((temp3[-1] + temp2[i]) % mod)
temp4 = {}
for i in temp3:
    temp4.setdefault(i, 0)
    temp4[i] += 1
ans = 0
for i in temp4.values():
    ans += (i * (i - 1) // 2)
print(ans)

Solution (Python):


from collections import defaultdict

con = 10 ** 9 + 7

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


def main():
	S = list(input())
	N = len(S)
	D = defaultdict(int)
	D[0] = 1
	var = 0
	for i in range(N):
		var = var + pow(10, i, 2019) * int(S[N - 1 - i])
		var %= 2019
		D[var] += 1

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

	print(ans)
	


if __name__ == '__main__':
	main()

Solution (Python):
s = input()

mods0 = [1]
for i in range(len(s)):
    tmp = mods0[-1] * 10
    mods0.append(tmp % 2019)

mods = [0]
for i in reversed(range(len(s))):
    tmp = mods[-1] + int(s[i]) * mods0[len(s) - i - 1]
    mods.append(tmp % 2019)

from collections import Counter
c = Counter(mods)
ans = 0
for key in c.keys():
    v = c[key]
    ans += v * (v - 1) // 2
print(ans)

Solution (Python):
s = input()[::-1]
n = len(s)
ans = 0
data = [0 for _ in range(2019)]
now = 0
data[0] = 1
q = [1]
x = 1
for i in range(n):
    x *= 10
    x %= 2019
    q.append(x)

for i,x in enumerate(s):
    now += int(x)*q[i]
    now %= 2019
    data[now] += 1
    

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

print(ans)

Solution (Python):
import collections
s=list(input())
n=len(s)
s.reverse()
l=[0]
a=1
x=0
for i in range(n):
  x+=a*int(s[i])
  x%=2019
  a*=10
  a%=2019
  l.append(x)
L=collections.Counter(l)
L2=list(L.values())
ans=0
for i in range(len(L2)):
  ans+=L2[i]*(L2[i]-1)//2
print(ans)

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

ct = Counter()
ct[0] = 1
ans = 0
tmp = 0
digit = 1
for c in S[::-1]:
    c = int(c)
    tmp = c * digit + tmp
    tmp %= MOD
    ans += ct[tmp]
    ct[tmp] += 1
    digit *= 10
    digit %= MOD
print(ans)

Solution (Python):
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

S = input()
L = len(S)
S = S[::-1]

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

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

Solution (Python):
from collections import defaultdict
S = [int(x) for x in input()]
N = len(S)
l = 1
ans = 0
dic = defaultdict(int)
dic[0] = 1
m = 0
for x in S[::-1]:
    m = (x * l + m) % 2019
    ans += dic[m]
    l = l * 10 % 2019
    dic[m] += 1
print(ans)

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    S = input().strip()

    D = {0: 1}
    ss = 0
    r = 1
    for s in S[::-1]:
        ss += int(s) * r
        ss %= 2019
        D[ss] = D.setdefault(ss, 0) + 1
        r *= 10
        r %= 2019

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


if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    k = min(k, n - k)
    ans = 1
    for i in range(1, k + 1):
        ans *= n - i + 1
        ans //= i
    return ans


s = input()
n = len(s)
a = [0] * (n + 1)
a[n - 1] = int(s[n - 1])
base = 10
for i in reversed(range(n - 1)):
    a[i] = (a[i + 1] + int(s[i]) * base) % 2019
    base *= 10
    base %= 2019


cnt = Counter(a)


ans = 0
for v in cnt.values():
    ans += comb(v, 2)

print(ans)

Solution (Python):
def examA():
    S, W = LI()
    if S<=W:
        print("unsafe")
    else:
        print("safe")
    return

def examB():
    A, B, C, D = LI()
    while(True):
        C -= B
        if C<=0:
            print("Yes")
            break
        A -= D
        if A<=0:
            print("No")
            break
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    Set = set(S)
    ans = len(Set)
    print(ans)
    return

def examD():
    S = SI()
    N = len(S)
    D = [0]*(N+1)
    for i in range(N):
        D[i+1] = (D[i]+int(S[N-1-i])*pow(10,i,2019))%2019
    
    ans = 0
    C = Counter(D)
    
    for c in C.values():
        ans += (c-1)*c//2
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""