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()
S = S[::-1]
L = [0]
i = 0
for x in S:
    tmp = L[-1] + pow(10, i , 2019) * int(x) 
    L.append(tmp % 2019)
    i += 1
L = sorted(L[1::])
def counter(array):
    from collections import Counter
    return list(Counter(array).most_common())
c = counter(L)
from math import factorial
def comb(n,r):
    if n == 1: return 0
    return  n * (n - 1) // 2
ans = 0
for x in c:
    if x[0] == 0: ans += x[1]
    ans += comb(x[1],2)
print(int(ans))

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

rem = [0]*P
mod = 0
ten = 1
rem[mod]=1
for i in range(N):
    mod=(mod+int(S[N-i-1])*ten)%P
    ten=ten*10%P
    rem[mod]+=1
for j in rem:
    ans+=(j*(j-1))//2
print(ans)

Solution (Python):
from math import pow
def get_table():
    table = []
    for i in range(10):
        a = int(pow(10, i))
        table.append(a % 2019)
    return table

table = get_table()


def get_power_2019(idx):
    if (idx < len(table)):
        return table[idx]
    else:
        j = int(idx/2)
        i = idx - j
        return (get_power_2019(i) * get_power_2019(j)) % 2019

for i in range(10, 10000):
    curr = get_power_2019(i)
    table.append(curr)

s = input()
mod_dict = {}

last_mod = 0
for i in range(len(s)-1, -1, -1):
    current_lowest_digit = int(s[i])
    current_mod = ((current_lowest_digit * get_power_2019(len(s)-1-i))% 2019 + last_mod) % 2019
    if (current_mod not in mod_dict.keys()):
        mod_dict[current_mod] = [i]
    else:
        mod_dict[current_mod].append(i)
    last_mod = current_mod



count = 0
for k in mod_dict.keys():
    n = len(mod_dict[k])
    count += int(n*(n-1)/2)
    if (k == 0):
        count += n
print(count)

Solution (Python):
S = list(input())
rest = [0] * (len(S) + 1)
rest[0] = 0
rd = 1
for i in range(len(S)):
    rest[i+1] = (rest[i] + int(S[-(i+1)]) * rd) % 2019
    rd *= 10
    rd %= 2019
    

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

Solution (Python):


s=input()
ans=0
p = 2019
n = len(s)
s=s[::-1]
accum=[0]*n
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
    
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):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 main():
    s = S()
    k = 2019
    tens = [1 for _ in range(len(s)+1)]
    for i in range(1, len(s)+1):
        tens[i] = tens[i-1] * 10 % k

    mods0toi = [0 for _ in range(len(s))]
    cur = 0
    for i in range(len(s))[::-1]:
        j = len(s) - i - 1
        mods0toi[i] = (cur + int(s[i]) * tens[j]) % k
        cur = mods0toi[i]
    s = collections.Counter(mods0toi)
    ans = 0
    t = s.keys()
    for c in t:
        if c == 0:
            ans += s[c]
        ans += (s[c]) * (s[c] - 1) // 2
    print(ans)

main()

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

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

print(result)

Solution (Python):
s = input()

res = [0 for i in range(2019)]
res[0] += 1

resten = 1
ressum = int(s[-1])
res[ressum] += 1

for i in range(2, len(s)+1):
    resten = (resten*10)%2019
    ressum = (int(s[-i])*resten + ressum)%2019
    res[ressum] += 1

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

Solution (Python):


import sys

read = sys.stdin.buffer.read

readlines = sys.stdin.buffer.readlines

s = input()
n = len(s)
mod = 2019
cum = [0] * (n + 1)
cum[0] = 0
for i in range(n):
    
    cum[i + 1] = (cum[i] * 10 + int(s[i])) % mod

mod_cum = [0] * (n + 1)
for i in range(n + 1):
    mod_cum[i] = (cum[i] * pow(10, n - i, mod)) % mod

mod_cum.sort()

ans = 0
cnt = 1
tmp = mod_cum[0]
for i in range(n):
    if mod_cum[i + 1] == tmp:
        cnt += 1
    else:
        tmp = mod_cum[i + 1]

        if cnt > 1:
            
            ans += cnt * (cnt - 1) // 2
        cnt = 1
if cnt > 1:
    ans += cnt * (cnt - 1) // 2
print(ans)

Solution (Python):
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    md=2019
    s=SI()
    n=len(s)
    vv=[0]*(n+1)
    ten=1
    for i in range(n-1,-1,-1):
        vv[i]=(vv[i+1]+int(s[i])*ten)%2019
        ten=(ten*10)%md
    vc=Counter(vv)
    ans=0
    for c in vc.values():
        ans+=c*(c-1)//2
    print(ans)

main()

Solution (Python):
S = input()
N = len(S)
C = [0 for i in range(2019)]
C[0] = 1
now = 0
tenfactor = 1

for i in range(N):
    s = int(S[-i-1])
    now = (now + s*tenfactor)%2019
    tenfactor = tenfactor*10%2019
    C[now] += 1
ans = 0
for i in range(2019):
    ans += C[i]*(C[i]-1)//2
print(ans)

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

a = 0
r = [0 for _ in range(m+1)]
r[0] = 1
z = 0
j = 1
for i in range(0,n):
    j = j * 10 % m
    ss = int(s[n-i-1])*j + z
    z = ss%m



    a += r[z]
    r[z] += 1

print(a)

Solution (Python):
from collections import Counter
s = input()[::-1]
n = len(s)
ans = 0
tmp_3, tmp_673 = 0, 0
c = Counter()
c[(0, 0)] = 1
for i in range(n):
	tmp_3 += int(s[i]) * pow(10, i, 3)
	tmp_3 %= 3
	tmp_673 += int(s[i]) * pow(10, i, 673)
	tmp_673 %= 673
	ans += c[(tmp_3, tmp_673)]
	c[(tmp_3, tmp_673)] += 1
print(ans)

Solution (Python):
from collections import Counter

S = input()
S = S[::-1]
base = 2019
count = 0
mod_list = [0]
ten = 1
for i in range(len(S)):
    mod = (ten*int(S[i]))%base
    mod_list.append((mod+mod_list[i])%base)
    ten*= 10
    ten%= base

c = Counter(mod_list)

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

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

p=1
q=[0]*448
for z in range(0,448):
    q[z]=p%2019
    p=10*q[z]

d=[0]*n   
for j in range(1,n+1):
    f=(n-j)%448
    d[j-1]=q[f]*t[j]%2019
ds=sorted(d)
ct=0
ans=0
if ds[0]==0:
    ct=1
    ans=1
for i in range(n-1):
    if ds[i+1]==ds[i]:
        ct+=1
        ans+=ct
    else:
        ct=0
print(ans)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

mod = 2019
s = input()
rui = []
ima = 0
ten = []
ten = 1
ss = [0]*len(s)
for i in reversed(range(len(s))):
    num = int(s[i])*ten
    ss[i] = num % mod
    ten *=10
    ten %= mod

ima = 0
for i in reversed(range(len(ss))):
    ima +=  int(ss[i])
    ima = ima % mod
    rui.append(ima)
dp = [0]*mod
for  i in range(len(rui)):
    dp[rui[i]] += 1
ans = dp[0]
for i in range(mod):
    tmp = dp[i] 
    ans += tmp*(tmp-1)//2
print(ans)

Solution (Python):
from collections import Counter

S = input()


p = 2019 
N = len(S)


m = [(int(S[i]) * pow(10, N-i, p)) % p for i in range(N)]


r = [0] * N
r[0] = m[0]
for ri in range(1, N):
    r[ri] = (r[ri-1] + m[ri]) % p


c = Counter(r)

ans = 0
for ci in [cv for cv in c.values() if cv >= 2]:
    ans += ci * (ci-1) // 2

if 0 in c.keys():
    ans += c[0]

print(ans)

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

if n<=4:
  print('0')
  exit()  

yo_list1=[1,10,100,1000]
yo1=1000
for i in range(200000):
  yo1 = yo1*10 % 2019
  yo_list1.append(yo1)

yo_dict = {i:0 for i in range(2019)}

yo2=int(s[n-1])
yo_dict[0]=1
yo_dict[yo2]=1

for i in range(1,n):
  yo2 = ( int(s[n-1-i])*yo_list1[i] + yo2 ) % 2019
  yo_dict[yo2]+=1

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

Solution (Python):
from collections import defaultdict
s=input()
n=len(s)
N=defaultdict(int)
x=0
for i in reversed(range(n)):
    x+=int(s[i])*pow(10,(n-i-1),2019)
    x%=2019
    N[x]+=1
ans=N[0]
for j in N.values():
    ans+=j*(j-1)//2
print(ans)

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

s_len = len(s)
ref = [0] * s_len

for i in range(1, s_len + 1):
    ref[-i] = int(s[-i]) * pow(10, i, MOD) % MOD

for i in range(1, s_len):
    ref[-i - 1] += ref[-i]
    ref[-i - 1] %= MOD

ref_cnt = Counter(ref)
ans = sum(ref_cnt.values()) - len(ref_cnt)


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

if 0 in ref:
    ans += ref_cnt[0]

print(ans)

Solution (Python):
N = 2019
cnt = [0] * N
S = input()
ans = 0
for s in S:
    s = int(s)
    new = [0] * N
    for n in range(N):
        idx = (10 * n + s) % N
        new[idx] += cnt[n]
    cnt = new
    cnt[s] += 1
    ans += cnt[0]
print (ans)

Solution (Python):
s = input()
p = 2019
n = len(s)
ans = 0

d = [0 for _ in range(n + 1)]
ten = 1

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

cnt = [0 for _ in range(p)]
for i in range(n, -1, -1):
    ans += cnt[d[i]]
    cnt[d[i]] += 1


print(ans)

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 collections import Counter

S = input()

"""
counts = Counter()
total = 0
for d in S:
    d = int(d)
    nextCounts = Counter()
    nextCounts[d] += 1
    for k, v in counts.items():
        nextCounts[(10 * k + d) % 2019] += v

    counts = nextCounts
    total += counts[0]
    

print(total)

"""

"""
def modInverse(a, m):
    m0 = m
    y = 0
    x = 1

    if m == 1:
        return 0

    while a > 1:

        
        q = a // m

        t = m

        
        
        m = a % m
        a = t
        t = y

        
        y = x - q * y
        x = t

    
    if x < 0:
        x = x + m0

    return x
"""




div10 = 202

mInv = 1

off = 0
counts = [0 for i in range(2019)]
total = 0
for d in S:
    d = int(d)
    off = (10 * off + d) % 2019
    
    mInv = (mInv * div10) % 2019
    
    counts[((d - off) * mInv) % 2019] += 1
    total += counts[((0 - off) * mInv) % 2019]

print(total)

Solution (Python):

MOD = 2019
S = input()
N = len(S)
X = [0]*2100
X[0] += 1
tmp = 0
hoge = pow(10,N,2019)

for i in range(N):
    tmp = (tmp*10+int(S[i]))%MOD
    hoge = (hoge*202)%MOD 
    X[(tmp*hoge)%MOD] += 1

ans = 0

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

print(ans)

Solution (Python):
s=input()
dic=dict()
accum=0
exp=1
dic[0]=1
ans=0
length=len(s)
for i in range(length):
  temp=exp*int(s[length-i-1])
  exp*=10
  exp%=2019
  accum+=temp
  accum%=2019
  if accum in dic:
    ans+=dic[accum]
    dic[accum]+=1
  else:
    dic[accum]=1
print(ans)

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

sys.setrecursionlimit(10**7)
INF = 10**10

N = 2019
cnt = [0] * N


def dec(cnt,s):
    new = [0] * N
    for n in range(N):
        idx = (10 * n + s) % N
        new[idx] += cnt[n]
    return new


S = input()[:-1]
ans = 0
for s in S:
    s = int(s)
    cnt = dec(cnt,s)
    cnt[s] += 1
    ans += cnt[0]
    
    
print (ans)

Solution (Python):
P = 2019
S = input()
N = len(S)
res = 0
 
if P in [2,5]:
    for i in range(N):
        if int(S[i])% P == 0:
            res += i+1
else:
    dic = {0:1}
    t1 = 0
    t2 = 1
    for i in range(N):
        t2 = (10*t2) % P
        t1 = (int(S[N-1-i])*t2 + t1) % P
        if t1 in dic:
            res += dic[t1]
            dic[t1] += 1
        else:
            dic[t1] = 1
 
print(res)

Solution (Python):
P = 2019
S = input()
N = len(S)
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):
S = input()
N = len(S)
C = [0 for i in range(2019)]
C[0] = 1
now = 0
tenfactor = 1

for i in range(N):
    s = int(S[-i-1])
    now = (now + s*tenfactor)%2019
    tenfactor = tenfactor*10%2019
    C[now] += 1
ans = 0
for i in range(2019):
    ans += C[i]*(C[i]-1)//2
print(ans)

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

S = list(map(int, readline().strip()))
N = len(S)
C = Counter()
C[0] = 1
ans = 0
MOD = 2019
res = 0
for i in range(N):
    s = S[N-1-i]
    res = (res+s*pow(10, i, MOD))%MOD
    ans += C[res]
    C[res] += 1
print(ans)

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

def solve(S,P):
    S = S[::-1]
    T = [0] * len(S)
    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)
    return sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]
print(solve(S,P))

Solution (Python):
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

s=input()
su=[0 for _ in range(len(s))]
su[0]=int(s[-1])
for i in range(1,len(s)):
    ii=len(s)-i-1
    o=int(s[ii])*pow(10,i,2019)
    su[i]=(su[i-1]+o)

    su[i]%=2019
su=su+[0]
a_dic=Counter(su)
ans=0

for i in a_dic.keys():
    if a_dic[i]<2:
        continue
    ans+=combinations_count(a_dic[i],2)

print(ans)

Solution (Python):
s=input()
a=len(s)
b=a-4
c=0
mod=2019
num=[0]*mod
num[0] = 1
now=0
ans=0
_10 = 1
for i in range(a-1, -1, -1):
    now=(now+int(s[i])*_10)%mod
    _10*=10
    _10%=mod
    ans+=num[now]
    num[now]+=1
print(ans)

Solution (Python):

s = input()
c = 0
mod = 2019
s_int = list(map(int, list(s)))

tens = [1]
for k in range(len(s)):
    tens.append((tens[-1] * 10)%mod )

ms = []
m = s_int[-1]%mod
ms.append(m)
for i in range(len(s) - 1)[::-1]:
    m = s_int[i] * tens[len(s) - i - 1] +  m
    m = m %mod
    ms.append(m)
    if m == 0:
        c += 1
        
from collections import Counter
co = Counter(ms)
for v in co.values():
    c += v * (v - 1) // 2

print(c)

Solution (Python):
from collections import Counter
  
P = 2019
S = input()
N = len(S)

ans = 0
S = S[::-1]
a, temp = [int(S[0]) % P], 1
for i in range(1, N):
    temp *= 10
    temp %= P
    val = (a[i-1] + (int(S[i]) % P * temp) % P) % P
    a.append(val)    
    
c = Counter(a)
if 0 in c:
    ans += c[0]
    ans += c[0] * (c[0] - 1) // 2
    del c[0]
for x in c.keys():
    ans += c[x] * (c[x]-1) // 2 
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):
from itertools import combinations
s = input()
d = {0: 1}
tmp = 0
i = 0
for char in s[::-1]:
    tmp += int(char) * pow(10, i, 2019)
    tmp %= 2019
    if tmp not in d:
        d[tmp] = 1
    else:
        d[tmp] += 1
    i += 1

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

print(result)

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

T=[]
now=1
for i in range(n):
    T.append(now*int(S[-i-1])%mod)
    now=now*10%mod
C=[]
now=0
for i in range(n):
    now+=T[i]
    now%=mod
    C.append(now)
C.sort()
now=0
cnt=1
A=[]
for i in range(n):
    if now==C[i]:
        cnt+=1
    else:
        if cnt>=2:
            A.append(cnt)
        now=C[i]
        cnt=1
if cnt>=2:
    A.append(cnt)

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

Solution (Python):



import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def binary(n):
    return bin(n)[2:]


def pow_by_binary_exponentiation(a, x, n): 
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y


def pow_by_montgomery_ladder(a, x, n): 
    x = [int(b) for b in binary(x)[::-1]]
    k = len(x)
    a1 = a
    a2 = a**2
    for i in range(k - 2, -1, -1):
        if x[i] == 0:
            a2 = (a1 * a2) % n
            a1 = (a1**2) % n
        else:
            a1 = (a1 * a2) % n
            a2 = (a2**2) % n
    return a1

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

s=input()

su=[0 for _ in range(len(s))]
su[0]=int(s[-1])
for i in range(1,len(s)):
    ii=len(s)-i-1
    o=int(s[ii])*pow(10,i,2019)
    
    
    su[i]=(su[i-1]+o)

    su[i]%=2019
a_dic=Counter(su)


ans=0
if 0 in a_dic.keys():
    ans+=a_dic[0]

for i in a_dic.keys():
    if a_dic[i]<2:
        continue
    ans+=combinations_count(a_dic[i],2)

print(ans)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = str(onem())

dp = [0 for i in range(2019)]
ans = 0
dp[0] = 1
dp[int(n[-1])] = 1
ten = 1
po = int(n[-1])
for i in range(len(n)-2,-1,-1):
    ten *= 10
    ten %= 2019
    po += ten*int(n[i])
    po %= 2019
    
    ans += dp[po]

    dp[po] += 1
    



print(ans)

Solution (Python):
def input_one_number():
    return int(input())

def input_multiple_number():
    return map(int, input().split())

def input_multiple_number_as_list():
    return list(map(int, input().split()))
 
mod = 2019
S = input()
 
checklist = [0] * mod
checklist[0] = 1
ans = 0
obs = 1
now = 0
for i in range(len(S)-1, -1, -1):
    now = (now + int(S[i]) * obs) % mod
    obs = (obs*10)%mod
    ans += checklist[now]
    checklist[now] += 1
 
print(ans)

Solution (Python):
s = str(input())
p = 2019
mod = [0]*2019
mod[0] += 1
now = 0
_10 = 1
for i in range(len(s)-1, -1, -1):
  now = (now + int(s[i])*_10) % p
  _10 *= 10
  _10 %= p
  mod[now] += 1
ans =  0
for i in mod:
  ans += i*(i-1)//2
print(ans)

Solution (Python):
s=input()
n=len(s)
rst=[0 for j in range(2019)]
rst[0]=1
x=0
ans=0
drst=1
for i in range(n):
    y=(int(s[n-1-i])*drst)%2019
    drst=(drst*10)%2019
    x+=y
    if x>=2019:
        x%=2019
    
    ans+=rst[x]
    rst[x]+=1

    

print(ans)

Solution (Python):
from collections import defaultdict

d = defaultdict(int)
d[0] = 1
s, p = 0, 1
for c in reversed(input()):
  s = (s + p * int(c)) % 2019
  d[s] = d.get(s, 0) + 1
  p = p * 10 % 2019
print(sum(x * (x - 1) // 2 for x in d.values()))

Solution (Python):
def resolve():
    s = [int(i) for i in input()]
    p_cnt = 0

    p = 2019

    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)
    
resolve()

Solution (Python):
import sys
from collections import Counter, defaultdict
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

S = read().decode().rstrip()

reminders = defaultdict(lambda: 0)
tmp = 0
mul = 1

for c in S[::-1]:
    c = int(c)
    tmp = (tmp + c * mul) % 2019
    mul = mul * 10 % 2019
    reminders[tmp] += 1
reminders[0] += 1

ans = 0

for r, cnt in reminders.items():
    ans += cnt * (cnt - 1) // 2

print(ans)

Solution (Python):
import os

import math
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def get_factors(n):
    """
    素因数分解
    :param int n:
    :rtype: list of int
    """
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


S = sys.stdin.buffer.readline().decode().rstrip()
N = len(S)
MOD = 2019

hist = []
mod_counts = [0] * MOD
power = 1
n = 0
for i in reversed(range(N)):
    n += int(S[i]) * power
    n %= MOD
    mod_counts[n] += 1
    hist.append(n)
    power *= 10
    power %= MOD

ans = 0
m = 0
power = 1
for i in reversed(range(N)):
    
    ans += mod_counts[m]
    mod_counts[hist[~i]] -= 1

    m += int(S[i]) * power
    m %= MOD
    power *= 10
    power %= MOD
print(ans)



def test(S, mod):
    ans = 0
    for l in range(len(S)):
        for r in range(l + 1, len(S) + 1):
            n = int(S[l:r])
            if n % mod == 0:
                print(n)
                ans += 1
    print(ans)

Solution (Python):
S = input()
N=len(S)
M = [0 for _ in range(2019)]

M[0]+=1
old = 0
for i in range(N):
    new_s = int(S[N-1-i])*pow(10,i,2019)
    new = (new_s + old) % 2019
    M[new] += 1
    old = new
count = 0
for m in M:
    count += int(m*(m-1)/2)
print(count)

Solution (Python):
d = {0: 1}
s, p = 0, 1
for c in reversed(input()):
  s = (s + p * int(c)) % 2019
  d[s] = d.get(s, 0) + 1
  p = p * 10 % 2019
print(sum(x * (x - 1) // 2 for x in d.values()))

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):
p = 2019
s = input()
n = len(s)
l = [0 for i in range(p)]
l[0] = 1
ten = 1
cnt = 0
 
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    for i in range(n):
        cnt = (cnt + int(s[-i-1]) * ten) % p
        l[cnt] += 1
        ten = (ten * 10) % p
    for i in l:
        if i > 1:
            ans += i * (i - 1) // 2
print(ans)

Solution (Python):
s = input()
n = len(s)
p = 2019
 
 
 
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
 
if 10 % p == 0:
	ans = 0
	for i in range(n):
		if int(s[n-1-i]) % p == 0:
			ans += n - i
	print(ans)
else:
	ans = pcnt[0]
	for num in pcnt:
		if num != 0:
			ans += num * (num - 1) // 2
 
	print(ans)

Solution (Python):
import collections
s = input()
mods = [0]
crt = 0
ans = 0
if len(s) <= 4:
    print(0)
    exit()





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

mods_count = collections.Counter(mods)
mods_count = list(mods_count.values())
for i in range(len(mods_count)):
    tar = mods_count[i]
    ans += tar*(tar-1)//2
print(ans)

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

ak10k = [(pow(10,n-k-1,m)*int(s[k]))%m for k in range(0,n)]+[0]

ruiseki=[0]*n
ruiseki[0]=ak10k[0]
for i in range(1,n):
    ruiseki[i]=(ruiseki[i-1]+ak10k[i])%2019

from collections import Counter
c = Counter(ruiseki)

ans=sum(cc*(cc-1)//2 for cc in c.values()) + c[0]

print(ans)

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

S = input()

P = 2019
N = len(S)

def solve_2(S):
    ind = (i for i, x in enumerate(S, 1) if x % 2 == 0)
    return sum(ind)

def solve_5(S):
    ind = (i for i, x in enumerate(S, 1) if x % 5 == 0)
    return sum(ind)

def solve(S,P):
    if P == 2:
        return solve_2(S)
    if P == 5:
        return solve_5(S)
    S = S[::-1]
    T = [0] * len(S)
    T[0] = int(S[0]) % P
    power = 1
    for i in range(1, len(S)):
        power *= 10
        power %= P
        T[i] = T[i-1] + power * int(S[i])
        T[i] %= P
    counter = Counter(T)
    return sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]


print(solve(S,P))

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

    S = list(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)


if __name__ == "__main__":
    main()

Solution (Python):
import math
import fractions
import collections
import itertools
from collections import deque
d=collections.deque()
S=list(input())
N=len(S)
cnt=0

amari=[0]*(N+1)
num=0
for i in range(N):
    d.append(int(S[i]))

for i in range(N):
    n=d.pop()
    num=(num+pow(10,i,2019)*n)%2019
    amari[i+1]=num



amari.sort()



buf=0

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



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

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

sum = 0
cnt = [0] * 2019
cnt[0] = 1
n = len(s)

for i in range(n):
    d = s[i] * pow(10, i, 2019)
    sum = (sum + d) % 2019
    cnt[sum] += 1
ans = 0
for i in range(2019):
    ans += cnt[i] * (cnt[i]-1)//2

print(ans)

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

mod = 2019
inv10 = 202
S = list(map(int, input()[:-1]))
N = len(S)
H = []
v = 0
d = 1
cusum = 0
M = [0] * mod
M[0] += 1
ans = 0
for c in S:
    h = c*d % mod
    d = d * inv10 % mod
    cusum = (cusum+h) % mod
    ans += M[cusum]
    M[cusum] += 1
print(ans)

Solution (Python):
S = input()

ten = [0] * (len(S) + 1)
ten[1] = 1
for i in range(1, len(S)):
    ten[i + 1] = ten[i] * 10 % 2019

accum = [0] * (len(S) + 1)
for i, v in enumerate(S[::-1]):
    accum[i + 1] = (int(v) * ten[i + 1] + accum[i]) % 2019

import numpy as np
bc = np.bincount(accum)
res = (bc * (bc - 1) // 2).sum()
print(res)

Solution (Python):
import collections

s=input()
l=len(s)
cnt=collections.defaultdict(int)
cnt[0]+=1
tmp=0
for i in range(l):
  tmp+=int(s[l-1-i])*pow(10,i,2019)
  tmp%=2019
  cnt[tmp]+=1
ans=0
for key in cnt.keys():
  ans+=(cnt[key]*(cnt[key]-1))//2
print(ans)

Solution (Python):
mod_673 = [1] * 672
for i in range(1,672):
    mod_673[i] = (mod_673[i -1] * 10) % 673

S = input()
S = S[::-1]
A = [0] * (len(S) + 1)
B = [0] * (len(S) + 1)
x = 0
Ans = [[0] * 3 for i in range(673)]
for i in range(1, len(S) + 1):
    A[i] = (A[i - 1] + int(S[i - 1]) * mod_673[(i - 1) % 672]) % 673
    B[i] = (B[i - 1] + int(S[i - 1])) % 3

for i in range(len(S) + 1):
    Ans[A[i]][B[i]] += 1

for i in range(673):
    for j in range(3):
        y = Ans[i][j]
        x += y * (y - 1) // 2

print(x)

Solution (Python):
S=input()

from collections import defaultdict
d=defaultdict(int)

n=len(S)
b=0
for i in range(n):
    a=int(S[n-i-1])
    b+=a*pow(10,i,2019)
    b%=2019
    d[b]+=1

ans=0

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

print(ans)

Solution (Python):
from functools import lru_cache



S=input()
count=[0 for i in range(2019)]
length=len(S)

S=S+'0'
S=S[::-1]
_S=0

base=1
for i,s in enumerate(S):
    _S=base*int(s)+_S
    count[_S%2019]+=1
    base*=10
    base=base%2019
    _S=_S%2019



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


print(retval)

Solution (Python):

S = list(map(int, list(input())))
N = len(S)
P = 673

cnt = [[0,0,0]  for i in range(P)]
cnt[0][0] = 1
rem1 = 0
rem2 = 0
ans = 0


for i in range(N):
    rem1 = (int(S[-i - 1]) * pow(10, i, P) + rem1) % P
    rem2 = (int(S[-i - 1]) * pow(10, i, 3) + rem2) % 3
    ans += cnt[rem1][rem2]
    cnt[rem1][rem2] += 1

print(ans)

Solution (Python):
a = input()

def int2019(s):
    s = [int(i) for i in s]
    modTable = [0] * 2019
    total = 0
    for i in range(len(s)):
        nextTable = [0] * 2019
        for j in range(2019):
            nextTable[(j * 10 + (s[i])) % 2019] = modTable[j]

        nextTable[(s[i]) % 2019] += 1
        total += nextTable[0]
        modTable = nextTable

    return total


print(int2019(a))

Solution (Python):
from collections import defaultdict
s = input()
n, p = len(s), 2019

dd = defaultdict(int)
dd[0] = 1
prev = 0

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

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

Solution (Python):
p = 2019 
D = input()
n=(len(D))
out = 0


if 10 % p == 0:
    for i in range(n):
        if int(D[i]) % p == 0:
            out += i + 1
else:
    mod = 0
    count = [0] * p
    ten = 1
    count[mod] += 1
    for i in range(n):
        mod = (mod + int(D[n-i-1]) * ten) % p
        ten = ten * 10 % p
        count[mod] += 1
    for c in count:
        out += (c * (c - 1)) // 2
print(out)

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

m=[0]*2019
m[0]=1
ans=0

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

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

print(ans)