Problem:
 Score : 400 points    Problem Statement Given is a string S consisting of digits from 1 through 9 .  Find the number of pairs of integers (i,j) ( 1 ≤ i ≤ j ≤ |S| ) that satisfy the following condition:  Condition: In base ten, the i -th through j -th characters of S form an integer that is a multiple of 2019 .      Constraints  1 ≤ |S| ≤ 200000  S is a string consisting of digits from 1 through 9 .         Input Input is given from Standard Input in the following format:  S       Output Print the number of pairs of integers (i,j) ( 1 ≤ i ≤ j ≤ |S| ) that satisfy the condition.        Sample Input 1 1817181712114      Sample Output 1 3  Three pairs - (1,5) , (5,9) , and (9,13) - satisfy the condition.       Sample Input 2 14282668646      Sample Output 2 2       Sample Input 3 2119      Sample Output 3 0  No pairs satisfy the condition.

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

def main():
    s = input().strip()
    mod = [0] * 2019

    tmp = 0
    ten = 10
    mod[tmp] += 1
    for i in range(len(s)-1, -1, -1):
        tmp = (tmp + ten * int(s[i])) % 2019
        ten = (ten * 10) % 2019
        mod[tmp] += 1
    ans = 0
    for i in range(2019):
        if mod[i] > 1:
            ans += (mod[i] * (mod[i] - 1)) // 2
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import defaultdict 
def main():
    s = readline().rstrip().decode()
    n = len(s)
    T = [0]
    P = 2019
    dd = defaultdict(int)
    dd[0] += 1
    for i in range(1, n+1):
        v = ((ord(s[-i])-ord('0'))*pow(10, i-1, P) + T[i-1])%P
        dd[v] += 1
        T.append(v)
    ans = 0
    for v in dd.values():
        ans += v*(v-1)//2
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
S = input()[::-1]
mod = 2019
d = defaultdict(int)
ruijo = 1
tmp = 0
for i in range(len(S)):
    tmp += int(S[i]) * ruijo % mod
    d[tmp % mod] += 1
    ruijo *= 10
    ruijo %= mod
ans = 0
for k, v in d.items():
    ans += v * (v - 1) // 2
    if k == 0:
        ans += v
print(ans)

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

dataset = [0]*2019
dataset[0] = 1

n = 0
d = 1

for i in s:
    n += int(i) * d
    a = n % 2019
    dataset[a] += 1
    d *= 10
    d %= 2019

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

print(count)

Solution (Python):
import collections
S=input()
l=len(S)
T,d=0,1
A=[0]*2019
A[0]=1
for i in range(l):
    T+=int(S[l-i-1])*d
    d*=10
    T%=2019
    d%=2019
    A[T]+=1
B=map(lambda x: x*(x-1)//2,A)
print(sum(B))

Solution (Python):
import collections
S=input()
l=len(S)
T,d=0,1
A=[0]*2019
A[0]=1
for i in range(l):
    T+=int(S[l-i-1])*d
    d*=10
    T%=2019
    d%=2019
    A[T]+=1
ans=0
for cnt in A:
    ans+=cnt*(cnt-1)//2
print(ans)

Solution (Python):
import collections
S=input()[::-1]
l=len(S)
T,d=0,1
A=[0]*2019
A[0]=1
for i in range(l):
    T+=int(S[i])*d
    d*=10
    T%=2019
    d%=2019
    A[T]+=1
ans=0
for cnt in A:
    ans+=cnt*(cnt-1)//2
print(ans)

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

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

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1

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

print(ans)

Solution (Python):
import sys
from collections import defaultdict as de


readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

s = ns()
digit = 1
ans = 0
num = 0
amari = de(int)
amari[0] = 1
"""
大筋のやり方は
https://drken1215.hatenablog.com/entry/2020/04/29/171300
を参照。

「この下のfor文について」
1211400を考える。
1万の桁を考えるとき
digit = 10000
digit = 1924 mod 2019
11400 = 10000 + 1400 = 1924 + 1400 = ans mod 2019
つまり、ある桁までの2019のあまりはその一つ下の桁までのあまりと
その桁の数*桁のあまりを足したもののあまりである
"""

for i in s[::-1]:
    num = num + int(i) * digit
    num %= 2019
    digit *= 10
    digit %= 2019
    amari[num] += 1

for j in amari.values():
    ans += j*(j-1)//2

print(ans)

Solution (Python):
from collections import defaultdict

s = input()

rests = [0]
n = 0
a = 0
m = 1
c = defaultdict(int)
c[0] += 1
for i in list(s)[::-1]:
    n = n + int(i)*m

    c[n % 2019] += 1
    m = m * 10 % 2019

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

Solution (Python):
S = input()
from collections import defaultdict
dic = defaultdict(int)
dic[0] += 1

S = S[::-1]
d = 1
now = 0
for i in range(len(S)):
    
    now += d*int(S[i]) % 2019
    dic[now%2019] += 1
    d *= 10
    d %= 2019
ans = 0
for k,v in dic.items():
    ans += v*(v-1)//2
print(ans)

Solution (Python):
import sys
tmp=sys.stdin.readline().rstrip()
def main():
   ans=0
   cnt=[0]*2019
   cnt[0]+=1
   t=0
   d=1
   for i in reversed(tmp):
      t=(t+int(i)*d)%2019
      cnt[t]+=1
      d=d*10%2019
   for i in cnt:
      ans+=i*(i-1)//2
   print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter

S = input()
MOD = 2019
div10 = 202  


def solve1(S):
    
    counts = [0 for i in range(MOD)]
    total = 0
    for d in S:
        d = int(d)
        nextCounts = [0 for i in range(MOD)]
        nextCounts[d] += 1
        for k, v in enumerate(counts):
            nextCounts[(10 * k + d) % MOD] += v
        counts = nextCounts
        total += counts[0]
    return total


def solve2(S):
    
    
    

    negPowTen = 1  
    prefix = 0  
    counts = [0 for i in range(MOD)]
    total = 0
    for d in S:
        d = int(d)
        prefix = (10 * prefix + d) % MOD
        negPowTen = (negPowTen * div10) % MOD
        counts[((d - prefix) * negPowTen) % MOD] += 1
        total += counts[((0 - prefix) * negPowTen) % MOD]
    return total


def solve3(S):
    
    
    
    
    
    
    
    
    
    
    
    negPowTen = 1
    total = 0
    prefix = 0
    counts = [0 for i in range(MOD)]
    counts[0] = 1
    for d in S:
        prefix = (prefix * 10 + int(d)) % MOD
        key = (prefix * negPowTen) % MOD
        total += counts[key]
        counts[key] += 1
        negPowTen = (negPowTen * div10) % MOD

    return total


def solve4(S):
    
    
    
    
    
    
    
    
    
    
    N = len(S)
    suf = 0
    powTen = 1
    counts = [0 for i in range(MOD)]
    total = 0
    counts[0] = 1
    for i in range(N):
        d = int(S[N - 1 - i])
        suf = (powTen * d + suf) % MOD
        total += counts[suf]
        counts[suf] += 1
        powTen = (powTen * 10) % MOD
    return total



ans = solve4(S)
print(ans)

Solution (Python):
from collections import Counter

S = input()
MOD = 2019
div10 = 202  


def solve1(S):
    
    counts = [0 for i in range(MOD)]
    total = 0
    for d in S:
        d = int(d)
        nextCounts = [0 for i in range(MOD)]
        nextCounts[d] += 1
        for k, v in enumerate(counts):
            nextCounts[(10 * k + d) % MOD] += v
        counts = nextCounts
        total += counts[0]
    return total


def solve2(S):
    
    
    

    negPowTen = 1  
    prefix = 0  
    counts = [0 for i in range(MOD)]
    total = 0
    for d in S:
        d = int(d)
        prefix = (10 * prefix + d) % MOD
        negPowTen = (negPowTen * div10) % MOD
        counts[((d - prefix) * negPowTen) % MOD] += 1
        total += counts[((0 - prefix) * negPowTen) % MOD]
    return total


def solve3(S):
    
    
    
    
    
    
    
    
    
    
    
    negPowTen = 1
    total = 0
    prefix = 0
    counts = [0 for i in range(MOD)]
    counts[0] = 1
    for d in S:
        prefix = (prefix * 10 + int(d)) % MOD
        key = (prefix * negPowTen) % MOD
        total += counts[key]
        counts[key] += 1
        negPowTen = (negPowTen * div10) % MOD

    return total


def solve4(S):
    
    
    
    
    
    
    
    
    
    
    N = len(S)
    suf = 0
    powTen = 1
    counts = [0 for i in range(MOD)]
    total = 0
    counts[0] = 1
    for i in range(N):
        d = int(S[N - 1 - i])
        suf = (powTen * d + suf) % MOD
        total += counts[suf]
        counts[suf] += 1
        powTen *= 10
    return total



ans = solve3(S)
print(ans)

Solution (Python):
from collections import Counter

S = input()
MOD = 2019
div10 = 202  


def solve1(S):
    
    counts = [0 for i in range(MOD)]
    total = 0
    for d in S:
        d = int(d)
        nextCounts = [0 for i in range(MOD)]
        nextCounts[d] += 1
        for k, v in enumerate(counts):
            nextCounts[(10 * k + d) % MOD] += v
        counts = nextCounts
        total += counts[0]
    return total


def solve2(S):
    
    
    

    negPowTen = 1  
    prefix = 0  
    counts = [0 for i in range(MOD)]
    total = 0
    for d in S:
        d = int(d)
        prefix = (10 * prefix + d) % MOD
        negPowTen = (negPowTen * div10) % MOD
        counts[((d - prefix) * negPowTen) % MOD] += 1
        total += counts[((0 - prefix) * negPowTen) % MOD]
    return total


def solve3(S):
    
    
    
    
    
    
    
    
    
    
    
    negPowTen = 1
    total = 0
    prefix = 0
    counts = [0 for i in range(MOD)]
    counts[0] = 1
    for d in S:
        prefix = (prefix * 10 + int(d)) % MOD
        key = (prefix * negPowTen) % MOD
        total += counts[key]
        counts[key] += 1
        negPowTen = (negPowTen * div10) % MOD

    return total


def solve4(S):
    
    
    
    
    
    
    
    
    
    
    N = len(S)
    suf = 0
    powTen = 1
    counts = [0 for i in range(MOD)]
    total = 0
    counts[0] = 1
    for i in range(N):
        d = int(S[N - 1 - i])
        suf = (powTen * d + suf) % MOD
        total += counts[suf]
        counts[suf] += 1
        powTen *= 10
    return total



ans = solve2(S)
print(ans)

Solution (Python):
s=input()
dic={}
cur=0
power=0
for i in range(0,len(s)+1):
  s_int=len(s)-i-1
  if cur in dic:
    dic[cur]+=1
  else:
    dic[cur]=1
  try:
    num=int(s[s_int])
    cur+=num*pow(10,power,2019)
    cur%=2019
    power+=1
  except IndexError:
    break

res=0
for i in range(len(dic)):
  t=dic.popitem()
  cc=t[1]
  res+=cc*(cc-1)//2
print(res)

Solution (Python):
s = list(input())
sur_list = [0 for i in range(2019)]
sur = 0
keta = 1
ans = 0

s.reverse()

for i in range(len(s)):
    keta = (keta*10)%2019
    sur_list[sur] += 1
    sur = (int(s[i]) * keta + sur) % 2019
    ans += sur_list[sur]

print(ans)

Solution (Python):
s=[int(x) for x in list(input())]
for c in range(len(s)-1,-1,-1):
    if c==len(s)-1:
        continue
    s[c]=(pow(10,len(s)-c-1,2019)*s[c]+s[c+1])%2019
s.append(0)
s.sort()
h=[1]
d=s[0]
for c in range(1,len(s)):
    if s[c]!=d:
        h.append(1)
        d=s[c]
    else:
        h[-1]+=1
k=[(x*(x-1))//2 for x in h]
print(sum(k))

Solution (Python):
import sys

input = sys.stdin.readline
P = 2019


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

    count = [0] * P
    count[0] += 1
    T = 0
    d = 1
    for s in reversed(S):
        T = (T + int(s) * d) % P
        count[T] += 1
        d = (d * 10) % P

    ans = 0
    for k in count:
        ans += k * (k - 1) // 2
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline
P = 2019


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

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

    ans = 0
    for k in count:
        ans = (ans + k * (k - 1) // 2)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
MOD = 2019

def solve(S):
    N = len(S)
    dp = [0 for _ in range(MOD)]
    tmp = 0
    ret = 0
    for i in range(N - 1, -1, -1):
        m = (tmp + int(S[i]) * pow(10, N - i - 1, MOD)) % MOD
        ret += dp[m]
        dp[m] += 1
        tmp = m
    ret += dp[0]
    return ret

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

Solution (Python):
MOD = 2019

def solve(S):
    N = len(S)
    dp = [0 for _ in range(MOD)]
    tmp = 0
    ret = 0
    for i in range(N):
        m = (tmp + int(S[i]) * pow(10, N - i - 1, MOD)) % MOD
        ret += dp[m]
        dp[m] += 1
        tmp = m
    ret += dp[0]
    return ret

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

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

Solution (Python):
s = input()
s = s[::-1]
m = [0] * 2019
m[0] = 1
a = 0
d = 1
ans = 0
for si in s:
    a = (a + int(si) * d) % 2019
    d = (d * 10) % 2019
    ans += m[a]
    m[a] += 1
print(ans)

Solution (Python):
s = input()
s = s[::-1]
n = len(s)
m = [0] * 2019
m[0] = 1
a = 0
d = 1
for i in range(n):
    a = (a + int(s[i]) * d) % 2019
    d = (d * 10) % 2019
    m[a] += 1
print(sum([int(x * (x - 1) / 2) for x in m if x > 1]))

Solution (Python):
s=input()
a=0
m={}
d=1
for i in range(len(s)):
  b=int(s[len(s)-1-i])*d+a
  b=b%2019
  a=b
  d=d*10%2019
  if b in m:
    m[b]+=1
  else:
    m[b]=1
if 0 in m:
  sum=m[0]
else:
  sum=0
for i in m:
  sum+=m[i]*(m[i]-1)/2
print(int(sum))

Solution (Python):




def nC2(n):
    return n * (n - 1) // 2
s = input()
n = len(s)
dp = [0] * 2020
mod = 2019
temp = 0
dp[0] = 1
for i in range(n):
    m = (int(s[i]) * pow(10, n - i - 1, mod) + temp)% mod
    dp[m] += 1
    temp = m
ans = 0
for i in range(2020):
    if dp[i]:
        ans += nC2(dp[i])
print(ans)

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

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

Solution (Python):
S = input()
amari = [0]*2019
ans = 0
amari[0] = 1
A = 0
for i in range(len(S)):
    A += pow(10, i, 2019)*(int(S[len(S)-1-i]))
    amari[A % 2019] += 1
for i in amari:
    if i >= 2:
        ans += i*(i-1)/2
print(int(ans))

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

S_mod = [0] * (len(S)+1)
S_mod[0] = int(S[0])

d = 10

for i in range(len(S)-1):
    S_mod[i + 1] = (S_mod[i] + int(S[i+1])*d)%2019
    d = d * 10 % 2019

mod_count = [0] * 2019
for i in range(len(S_mod)):
    mod_count[S_mod[i]] += 1
    
count = 0
for i in range(2019):
    count += mod_count[i] * (mod_count[i] - 1) / 2

print(int(count))

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

S_mod = [0] * (len(S)+1)
S_mod[0] = int(S[0])

mod_count = [0] * 2019

d = 10




for i in range(len(S)-1):
    S_mod[i + 1] = (S_mod[i] + int(S[i+1])*d)%2019
    d = d * 10 % 2019
    


for i in range(len(S_mod)):
    mod_count[S_mod[i]] += 1


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

Solution (Python):
from sys import stdin, setrecursionlimit


def main():
    mod = 2019
    input = stdin.buffer.readline
    s = list(map(int, list(input()[:-1].decode())))
    n = len(s)
    s.reverse()

    tmp_p10 = 1
    p10 = [tmp_p10]
    for _ in range(1, n + 1):
        tmp_p10 *= 10
        tmp_p10 %= mod
        p10.append(tmp_p10)

    tmp_mod = s[0] % mod
    mods = [0, tmp_mod]
    for i in range(1, n):
        tmp_mod = (s[i] * p10[i] + tmp_mod) % mod
        mods.append(tmp_mod)
    m2019 = [0] * 2019
    for mi in mods:
        m2019[mi] += 1
    ans = 0
    for mi in m2019:
        ans += mi * (mi - 1) // 2

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
def abc164_d():
    
    s = str(input())
    n = len(s)
    m = 2019
    srev = s[::-1]  
    x = 1  
    total = 0  
    cnt = [0] * m  
    ans = 0
    for i in range(n):
        cnt[total] += 1
        total += int(srev[i]) * x
        total %= m
        ans += cnt[total]
        x = x*10 % m
    print(ans)

abc164_d()

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

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

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

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

cnts = [0] * 2019
cnts[0] = 1

n, d = 0, 1

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

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

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
	s=input()
	len_s=len(s)
	T=[0]*(len_s+1)
	T[-1],T[-2]=0,int(s[-1])
	mod=2019
	for i in range(len_s-2,-1,-1):
		T[i]=(T[i+1]+int(s[i])*pow(10,len_s-i-1,mod))%mod
	tc=list(Counter(T).values())
	ans=0
	for tcc in tc:
		ans+=tcc*(tcc-1)//2
	print(ans)

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
	s=input()
	len_s=len(s)
	T=[0]*(len_s+1)
	T[-1],T[-2]=0,int(s[-1])
	mod=2019
	for i in range(len_s-2,-1,-1):
		T[i]=(T[i+1]+int(s[i])*pow(10,len_s-i-1,mod))%mod
	tc=list(Counter(T).values())
	ans=0
	for tcc in tc:
		ans+=tcc*(tcc-1)//2
	print(ans)

if __name__=='__main__':
    main()

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
n=len(S)
D=[0]*2019
T=[0]*(n+1)
T[0]=1
for i in range(n):
  T[i+1]=(T[i]*10)%2019

cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*T[keta])%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)

Solution (Python):
from collections import Counter

n = list(input())
n.reverse()
x = [0]*(len(n))
a=0
ex=1
for i in range(len(n)):
    a+=int(n[i])*ex
    x[i]=a%2019
    ex=ex*10%2019
c=Counter(x)
ans = c[0]
for i in c.keys():
    b=c[i]
    ans += b*(b-1)//2

print(ans)

Solution (Python):
S = list(str(input()))
S.reverse()
mod = 2019
rem = [0]*mod
num = 0
rem[num] += 1
d = 1
ans = 0
for s in S:
  num += int(s) * d
  num %= mod
  d *= 10
  d %= mod
  rem[num] += 1
for r in rem:
  ans += r*(r-1)//2
print(ans)

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

    l = [0]
    t = 1
    for i, x in enumerate(s[::-1]):
        t = t * 10 % 2019
        y = (l[-1] + int(x) * t) % 2019
        l.append(y)

    c = Counter(l)
    ans = sum([v * (v - 1) // 2 for v in c.values()])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import Counter
    from itertools import accumulate
    s = input()

    n = 2019
    l = [0]
    t = 1
    for i, x in enumerate(s[::-1]):
        t = t * 10 % n
        y = (l[-1] + int(x) * t) % n
        l.append(y)

    c = Counter(l)
    ans = accumulate([v * (v - 1) // 2 for v in c.values()])
    print(list(ans)[-1])


if __name__ == '__main__':
    main()

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

    n = 2019
    l = [0]
    t = 1
    for i, x in enumerate(s[::-1]):
        t = t * 10 % n
        y = (l[-1] + int(x) * t) % n
        l.append(y)

    c = Counter(l)
    ans = sum([v * (v - 1) // 2 for v in c.values()])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
MOD = 2019
def main():
    S = input()
    dp = [0] * (len(S)+1)
    ex = 1
    for i in range(len(S)):
        dp[i+1] = (int(S[-1-i])*ex + dp[i]) % MOD
        ex *= 10
        ex %= MOD
    d = defaultdict(int)
    for i in range(len(S)+1):
        d[dp[i]] += 1
    output = 0
    for i in d.keys():
        output += (d[i] * (d[i]-1) // 2)
    print(output)
    return

if __name__ == '__main__':
    main()

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

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

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

ans = 0
for i in cum[::-1]:
    ans += cnt[i]
    cnt[i] += 1
    if i == 0:
        ans += 1
print(ans)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
n = len(s)
t = []
for i in range(n):
    t.append(int(s[i])*pow(10, (n-i-1), 2019) % 2019)
t = list(accumulate(t))
t = [0] + [i % 2019 for i in t]
ans = 0
cnt = defaultdict(int)
for i in range(n+1):
    ans += cnt[t[i]]
    cnt[t[i]] += 1
print(ans)

Solution (Python):
def main():
    import collections
    s=list(map(int,input()))
    modpow=[1]*len(s)
    for i in range(1,len(s)):
        modpow[i]=(modpow[i-1]*10)%2019
    ans=0
    res=[0]*len(s)
    res[0]=s[-1]%2019
    for i in range(1,len(s)):
        res[i]=(modpow[i]*s[len(s)-1-i]+res[i-1])%2019
    res.append(0)
    c=collections.Counter(res).most_common()
    for i in range(len(c)):
        ans+=(c[i][1]*(c[i][1]-1)//2)
    print(ans)
if __name__=="__main__":
    main()

Solution (Python):
s = input()
s = s[::-1]
l = len(s)
se = dict()

k = 0
for i in range(0,l):
    k+=(pow(10,i,2019)*int(s[i]))
    k%=2019
    if k in se:
        se[k]+=1
    else:
        se[k]=1

ans=0
for j in se:
    i=se[j]
    if i>1:
        ans+=(i*(i-1)//2)
    if j==0:
        ans+=i
print(ans)

Solution (Python):
s=input()
l=len(s)
se=dict()
k=0
for i in range(l-1,-1,-1):
    k+=(pow(10,l-1-i,2019)*int(s[i]))
    k%=2019
    if k in se:
        se[k]+=1
    else:
        se[k]=1

ans=0
for j in se:
    i=se[j]
    if i>1:
        ans+=(i*(i-1)//2)
    if j==0:
        ans+=i
print(ans)

Solution (Python):
s=input()
l=len(s)
se=dict()
k=0
for i in range(l-1,-1,-1):
    k+=(pow(10,l-1-i,2019)*int(s[i]))
    k%=2019
    if k in se:
        se[k]+=1
    else:
        se[k]=1

ans=0
for j in se:
    i=se[j]
    if i>1:
        ans+=(i*(i-1)//2)
    if j==0:
        ans+=i
print(ans)

Solution (Python):
M = 2019
s = input()
tot, ten, ans = 0, 1, 0
cnt = [0] * M
for si in s[::-1]:
    cnt[tot] += 1
    tot += int(si) * ten
    tot %= M
    ans += cnt[tot]
    ten *= 10
    ten %= M
print(ans)

Solution (Python):


import itertools

s = input()[::-1]

d = len(s)


_map = [0]*2019
_map[0] = 1

ans = 0
j,_ = 1,0

for i in s:
    _ += int(i) * j
    _tmp = _ % 2019
    j = (j*10)%2019
    _map[_tmp] += 1
    
for _l in _map:
    ans += _l * (_l - 1) / 2
    
print(int(ans))

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

n = len(s)
cnt = [0] * 2019
cnt[0] = 1
total = 0
ans = 0
x = 1

for i in range(n):
    total += int(s[i]) * x
    total %= 2019
    x *= 10
    x %= 2019
    ans += cnt[total]
    cnt[total] += 1

print(ans)

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

s = 0 
c = [0] * 2019 
c[s] += 1
d = 1 

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

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

Solution (Python):
import sys

input = sys.stdin.readline

S = input().rstrip()
n = len(S)
l = [0]*2019
d = 10

t = int(S[n-1])
l[t%2019] += 1

l[0] += 1

for i in range(n-2, -1, -1):
    t += int(S[i])*d%2019
    l[t%2019] += 1 
    d *= 10
    d %= 2019

ans = 0

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

print(ans)

Solution (Python):
from sys import stdin, setrecursionlimit


def main():
    input = stdin.readline
    s = list(input()[:-1])[::-1]
    N = len(s)
    p10 = [1]
    tmp = 1
    for _ in range(N - 1):
        tmp = tmp * 10 % 2019
        p10.append(tmp)
    mod = []
    tmp = 0
    for num, p in zip(s, p10):
        tmp = (tmp + int(num) * p) % 2019
        mod.append(tmp)

    mod.sort()
    mod.insert(0, 0)

    ans = 0
    count = 1
    for i in range(1, N + 1):
        if mod[i] == mod[i - 1]:
            count += 1
        else:
            ans += count * (count - 1) // 2
            count = 1
    ans += count * (count - 1) // 2
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
s=input()
n=len(s)
a=0
t=1
d=[1]+[0]*2018

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

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

print(ans)

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

lst = []
num = 1
pow10 = [1]
for _ in range(len(s) - 1):
    num = num * 10 % 2019
    pow10.append(num)

num = 0
for s_num, p10 in zip(s, pow10):
    num = (num + (int(s_num) * p10)) % 2019
    lst.append(num)
lst.sort()

total = 0
cnt = 1
before = 0
for num in lst:
    if before == num:
        cnt += 1
    else:
        total += cnt * (cnt - 1) // 2
        cnt = 1
    before = num
total += cnt * (cnt - 1) // 2
print(total)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    S = input().rstrip()
    counter = defaultdict(int)
    mod = 2019
    counter[0] += 1
    num = 0
    d = 1
    for c in S[::-1]:
        num += int(c) * d
        num %= mod
        counter[num] += 1
        d *= 10
        d %= mod
    ans = 0
    for v in counter.values():
        ans += (v * (v-1)) // 2
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
S = input()
A = [0 for i in range(2019)]
x = 0
q = 1
for i in range(len(S)):
    p = i + 1
    a = (int(S[-p]))
    b = a*q%2019
    x = (x+b) % 2019
    A[x] += 1
    q = q*10%2019
ans = A[0]
for i in range(2019):
    ans += A[i]*(A[i]-1)//2
print(ans)

Solution (Python):
from collections import Counter
N = input()
S=0
mod_count=[0]
ans=0
i=0
for X in N[::-1]:
  S = int(X)*pow(10,i,2019) % 2019
  S=mod_count[i]+S
  mod_count.append(S%2019)
  i+=1

c = Counter(mod_count)
ans = sum(Y * (Y-1)/2 for Y in c.values())
print(int(ans))

Solution (Python):
import sys
import numpy as np
from numba import njit

MOD = 2019

@njit('(i4[::1],)', cache=True)
def f(S):
    dp = np.zeros(MOD, np.int64)
    temp = np.empty_like(dp)
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % MOD
        temp[x:] = dp[:-x]
        temp[:x] = dp[-x:]
        dp, temp = temp, dp
        answer += dp[0]
        pow10 *= 10
        pow10 %= MOD
    return answer


S = np.int32(list(input().rstrip()))
print(f(S))

Solution (Python):
from collections import Counter

S = str(input())

memo = [0]
d = 0
mod = 2019


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

c = Counter(memo)
ans = sum(v * (v-1)/2 for v in c.values())
print(int(ans))

Solution (Python):
MOD=2019
S=input()
N=len(S)
nums=[0]*N
nums[-1]=int(S[-1])%MOD
for i in range(-2, -N-1, -1):
  nums[i]=(int(S[i])*pow(10, -(i+1), MOD)+nums[i+1])%MOD

a=[0]*2019
for i in range(N):
  a[nums[i]]+=1
  
print(a[0]+sum([(a[i]*(a[i]-1))//2 for i in range(2019)]))

Solution (Python):
s = input()[::-1]
num = 0
last = 0
d = 1
count={}
for k in range(2019):
    count[k] = 0
    
count[0] =1  

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

Solution (Python):
import sys
input = sys.stdin.readline
mod = 2019
s = input().rstrip()
n = len(s)
mod_list = [0]
for i in range(n - 1, -1, -1):
    mod_list.append((mod_list[-1] + int(s[i]) * pow(10, n - 1 - i, mod)) % mod)
from collections import Counter
c = Counter(mod_list)
ans = 0
for i in c.keys():
    ans += c[i] * (c[i] - 1) // 2
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
mod = 2019
s = input().rstrip()
n = len(s)
mod_list = [0]
for i in range(n - 1, -1, -1):
    mod_list.append((mod_list[-1] + int(s[i]) * pow(10, n - 1 - i, mod)) % mod)
from collections import Counter
c = Counter(mod_list)
ans = 0
for i in c.keys():
    ans += c[i] * (c[i] - 1) // 2
print(ans)

Solution (Python):
import numpy as np

S = input()
MOD = 2019
dp = np.zeros(MOD, dtype=np.int64)
dp[0] = 1

def hoge(dp, s):
    T = dp.copy()
    dp[s:] = T[:-s]
    dp[:s] = T[-s:]

ans = 0
for i, s in enumerate(S[::-1]):
    hoge(dp, (int(s) * pow(10, i, MOD)) % MOD)
    ans += dp[0]
    dp[0] += 1
print(ans)

Solution (Python):
import numpy as np
from numba import njit

S = input()
MOD = 2019
dp = np.zeros(MOD, dtype=np.int64)
dp[0] = 1

@njit
def hoge(dp, s):
    T = dp.copy()
    dp[s:] = T[:-s]
    dp[:s] = T[-s:]

ans = 0
for i, s in enumerate(S[::-1]):
    hoge(dp, (int(s) * pow(10, i, MOD)) % MOD)
    ans += dp[0]
    dp[0] += 1
print(ans)

Solution (Python):

S=list(input())
mod=2019
S=list(reversed(S))
N=len(S)
A=[0]*(N)
p=1
for i in range(N):
    if i==0:
        p=1
    else:
        p*=10
        p%=mod
    now=(int(S[i])*p)%mod
    A[i]=now
    
rui=[0]*(N+1)
for i in range(1,N+1):
    rui[i]=(rui[i-1]+A[i-1])%mod
total=[0]*2019
for r in rui:
    total[r]+=1
ans=0
for t in total:
    ans+=t*(t-1)//2
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

s=SI()
n=len(s)
beki=[0 for i in range(n+1)]
beki[0]=1
for i in range(n):
    beki[i+1]=(beki[i]*10)%2019



dp=[0 for i in range(n)]
dp[-1]=int(s[-1])

for i in range(n-1):
    j=n-i-1
    
    dp[j-1]=(dp[j]+int(s[j-1])*beki[i+1])%2019


ans=0
u=Counter(dp)

for i in u:
    if i==0:
        ans+=(u[i]*(u[i]+1))//2
    else:
        ans+=(u[i]*(u[i]-1))//2
print(ans)

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

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

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

Solution (Python):
from sys import stdin
def nC2(n):
    return n*(n-1)//2

def main():
    
    readline=stdin.readline
    s=readline().strip()

    d=dict()
    p=1
    t=0
    for i in range(len(s)-1,-1,-1):
        n=int(s[i])
        m=(n*p+t)%2019
        t=m
        p*=10
        p%=2019
        if m not in d:
            d[m]=1
        else:
            d[m]+=1
        
    if 0 in d:
        ans=d[0]
    else:
        ans=0
    for v in d.values():
        ans+=nC2(v)
    print(ans)
    
if __name__=="__main__":
    main()

Solution (Python):
S = input()
lenS = len(S)
count = [0] * 2019
count[0] = 1
num = 0
d = 1
for i in range(lenS):
    num += int(S[lenS - i - 1]) * d
    count[num%2019] += 1
    d *= 10
    d %= 2019
ans = 0
for i in count:
    ans += i*(i-1)//2
print(ans)

Solution (Python):
s =list(str(input()))
s = [int(c) for c in s]
s.reverse()

n = len(s)
p = 2019

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

temp = 0
cum = [0]*n
for i in range(n):
    temp += s[i]*power(10, i, p)
    temp = temp%p
    cum[i] = temp
cum = [0]+cum



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