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
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

H, W = map(int, input().split())

L, R = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
D = list(map(int,input().split()))

L = list(map(int,input().split()))
R = list(map(int,input().split()))

T = list(map(int,input().split()))

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''


S = input()

N = len(S)


accum = [int(S[N - 1 - i]) for i in range(N)]

base = 1
for i in range(N-1):

    base*=10
    base %= 2019

    accum[i+1] = (accum[i] + base * accum[i+1]) % 2019







count = [0] * 2019

for a in accum:
    count[a] += 1




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

ans += count[0]

print(int(ans))

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

remainder=[0]*M
val=0
for i in range(N):
  val=(int(S[N-1-i])*pow(10,i,M)+val)%M
  remainder[val]+=1

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

Solution (Python):
from collections import defaultdict
def solve():
    S = input()
    d = defaultdict(int) 

    cur = 0
    tenFactor = 1
    d[cur] += 1
    for i in range(len(S)):
        cur = (cur + int(S[-i-1]) * tenFactor) % 2019
        tenFactor = tenFactor * 10 % 2019
        d[cur] += 1
    
    ans = 0
    for i in range(2019+1):
        ans += d[i] * (d[i]-1) // 2
    
    print(ans)

if __name__ == '__main__':
    solve()

Solution (Python):
S = str(input())
N = len(S)
ans1 = [0] * 2019
ans2 = 0

T = [0] *  (N + 1)
T[N] = 0
ans1[0] += 1

P = 1
for i in range(N - 1, -1, -1):
  
  T[i] = (T[i + 1] + P * int(S[i])) % 2019
  ans1[T[i]] += 1
  P = 10 * P % 2019

for i in range(2019):
  x = ans1[i]
  ans2 += x * (x - 1) / 2
  


print(int(ans2))

Solution (Python):
arr = [0 for i in range(2019)]
arr[0] = 1

s = input()
n = len(s)

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


ans = 0
for m in arr:
    if m==0: continue
    ans += m*(m-1)//2

print(ans)

Solution (Python):
s = input()
n = len(s)
ans = 0
now = 0
mp = [0 for i in range(2019)]
mp[0] += 1
tmp = [0 for i in range(2019)]

id = [0 for i in range(2019)]
for i in range(2019):
    id[i] = i * 10 % 2019

for c in s:
    now *= 10;
    now += ord(c) - ord("0")
    now %= 2019

    ans += mp[now]
    mp[now] += 1
    for i in range(2019):
        tmp[id[i]] = mp[i]
    for i in range(2019):
        mp[i] = tmp[i]

print(ans)

Solution (Python):

import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  
  sys.stderr.write(_s+"\n")


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

m = 2019

A=[0]*m
A[0]=1

a = 0
ans=0
for i,s in enumerate(S):
	a = a + (int(s) * pow(10,i,m))
	a %= m
	
	ans += A[a]
	A[a] += 1

print(ans)

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


smod = [0]
tmod = 0
keta = 1
for i in range(N):
    temp = tmod + int(S[(N-1)-i])*keta
    
    tmod = temp%2019
    smod.append(tmod)
    keta = keta*10%2019


cmod = Counter(smod)


ans = 0
for i in cmod.values():
    ans += i*(i-1)/2
print(int(ans))

Solution (Python):
mod2019=[0]*2019
mod2019[0]=1
t=input()
n=len(t)
s=[]
for i in range(n):
  s.append(int(t[i]))
x=1
y=0
for i in reversed(range(n)):
  y+=s[i]*x
  mod2019[y%2019]+=1
  x=(x*10)%2019
ans=0
for i in range(2019):
  ans+=mod2019[i]*(mod2019[i]-1)
print(ans//2)

Solution (Python):
import sys, math
from pprint import pprint
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

S = rs()


mods = []
n = 0
e = 0
for i in reversed(range(len(S))):
	n += int(S[i]) * pow(10,e,2019)
	
	e += 1
	
	mods.append(n % 2019)
mods.append(0)
import collections
cnt = collections.Counter(mods)
ans = 0
for k, c in cnt.items():
	ans += c*(c-1)//2
print(ans)

Solution (Python):
S = input()

N = len(S)
table = [-1] * N
T = [-1] * N
prev = 0
for i, s in enumerate(reversed(S)):
    prev += (int(s) * pow(10, i, 2019)) % 2019
    prev %= 2019
    T[i] = prev

DP = [0] * 2019
for t in T:
    DP[t] += 1

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

print(ans)

Solution (Python):
def main():
    import sys
    from collections import defaultdict
    dic = defaultdict(int)

    input = sys.stdin.readline

    s = str(input().rstrip())
    m = 0
    before_m = 0.1

    for i in range(1, len(s) + 1):
        before_m = int(before_m*10)%2019
        m_ad = (int(s[-i]) * before_m) % 2019
        m = (m_ad + m) % 2019
        dic[m] += 1

    ans1 = 0

    for x in dic.values():
        if x > 1:
            ans1 += x * (x - 1) // 2
    ans2 = dic[0]

    print(ans1 + ans2)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter

s = list(input())
ls = len(s)
T = [0] * (ls+1)
modL = [0]
cnt = 0
pad = 1

for i in reversed(range(0, ls)):
    T[i] = T[i+1] + int(s[i]) * pad
    modL.append(T[i] % 2019)
    pad = pad * 10 % 2019

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

print(ans)

Solution (Python):
s = input()
x = list(map(int, list(s)))
x = x[::-1]
dic = [0 for _ in range(2020)]
ten = 1
y = 0
for i in range(len(s)):
    y = (y+ten*x[i])%2019
    dic[y] += 1
    ten = (ten*10)%2019
result = 0
for i in range(2019):
    result += max([dic[i]*(dic[i]-1)//2, 0])
result += dic[0]
print(result)

Solution (Python):
S = input()
N = len(S)
a = []
for s in S:
    a.append(int(s))
MOD = 2019

cur = 0
cten = 0
li = [0 for i in range(MOD)]
for aa in reversed(a):
    if cten==0:
        cten = 1
    else:
        cten = (cten*10)%MOD
    cur = (aa*cten+cur)%MOD
    li[cur] += 1
    

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

Solution (Python):
s = input()
x = list(map(int, list(s)))
x = x[::-1]
dic = [0 for _ in range(2020)]
ten = 1
y = 0
for i in range(len(s)):
    y = (y+ten*x[i])%2019
    dic[y] += 1
    ten = (ten*10)%2019
result = 0
for i in range(2019):
    result += max([dic[i]*(dic[i]-1)//2, 0])
result += dic[0]
print(result)

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

count = [0] * P
count[0] = 1
u = 0
for i, s in enumerate(reversed(S)):
    u = (int(s) * pow(10, i, P) + u) % P
    ans += count[u]
    count[u] += 1
print(ans)

Solution (Python):
s = list(input())[::-1]
l = [0]*2019 
l[0] = 1
ten = 1
mod = 2019
now = 0
ans = 0
for i in range(len(s)):
    a = int(s[i])*ten
    now = (now+a)%mod
    ans += l[now]
    l[now] += 1
    ten *= 10
    ten %= 2019
print(ans)

Solution (Python):
S = input().strip()
A = [0 for _ in range(len(S))]
A[-1] = int(S[-1])%3
for i in range(2,len(S)+1):
    A[-i] = (A[-i+1]+int(S[-i]))%3
B = [0 for _ in range(len(S))]
B[-1] = int(S[-1])%673
a = 1
for i in range(2,len(S)+1):
    a = (a*10)%673
    B[-i] = (int(S[-i])*a+B[-i+1])%673
C = {}
for i in range(len(S)):
    a = A[i]
    b = B[i]
    if (a,b) not in C:
        C[(a,b)] = 0
    C[(a,b)] += 1
if (0,0) in C:
    C[(0,0)] += 1
cnt = 0
for c in C:
    n = C[c]
    cnt += (n*(n-1))//2
print(cnt)

Solution (Python):

S = input()
list_amari = [0 for i in range(2019)]
amari_prev = 0
X = 1

for i in range(len(S)):
  amari = (int(S[-i-1])*X+amari_prev)%2019
  list_amari[amari] += 1
  amari_prev = amari
  X = (10*X)%2019

count = list_amari[0]
for v in list_amari:
  count += v*(v-1)//2

print(count)

Solution (Python):
def main():
    S = list(input())
    N = len(S)

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


if __name__ == "__main__":
    main()

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):
def main():
  s=input()[::-1]
  l,mod=len(s),2019
  x=[0]*mod
  x[0]=1
  a,t=0,1
  for i in range(l):
    a = (a + int(s[i])*t) % 2019
    x[a]+=1
    t=(t*10)%mod
  ans=sum([i*(i-1)//2 for i in x])
  print(ans)
if __name__=='__main__':
  main()

Solution (Python):
import sys, math
from pprint import pprint
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

S = rs()

mods = []
n = 0
e = 1
for i in reversed(range(len(S))):
	n += int(S[i]) * e
	e = (e*10) % 2019
	n = n % 2019
	mods.append(n)
mods.append(0)
import collections
cnt = collections.Counter(mods)
ans = 0
for k, c in cnt.items():
	ans += c*(c-1)//2
print(ans)

Solution (Python):
s = input()
n = len(s)
table = [0 for _ in range(n + 1)]
for i in range(n):
    table[-2 - i] = (int(s[-1 - i]) * pow(10, i, 2019) + table[-1 - i]) % 2019
count = [0 for _ in range(2019)]
ans = 0
for t in table:
    if count[t] != 0:
        ans += count[t]
    count[t] += 1
print(ans)

Solution (Python):
import sys
import collections
from math import ceil

ma = lambda : map(int,input().split())
ni = lambda : int(input())
s = input()
n = len(s)
l = [0]*(n+1)
d = 1
mod = 2019
for i in range(1,n+1):
    l[i] = (l[i-1] + int(s[-i])*d)%mod
    d = d*10%mod

co = collections.Counter(l)
ans = 0
for cnt in co.values():
    ans+=cnt*(cnt-1)//2
print(ans)

Solution (Python):
a,*d=[0]*2020
for i in map(int,input()):
  p=[0]*2019
  for j in range(2019):p[(j*10+i)%2019]+=d[j]
  d=p
  d[i]+=1
  a+=d[0]
print(a)

Solution (Python):
def main():
    s = input()[::-1]
    sum_digits = 0
    cnts = [0] * 2019
    cnts[0] = 1
    d = 1
    for c in s:
        sum_digits += int(c) * d
        sum_digits %= 2019
        
        d *= 10
        d %= 2019
        cnts[sum_digits] += 1
    ans = 0
    for i, cnt in enumerate(cnts):
        
        ans += cnt * (cnt - 1) // 2
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
s = input()
if(len(s) < 5):
    print(0)
else:
    t = [0]*2019
    t[0] = 1
    p = 0
    temp = 0
    temp2 = 1
    for i in range(1,len(s)+1):
        temp2 *= 10
        temp2 %= 2019
        t[(temp + temp2*int(s[-i]))%2019] += 1
        temp += temp2*int(s[-i])
    for i in range(2019):
        p += (t[i]*(t[i]-1))//2
    print(p)

Solution (Python):
import sys
input = sys.stdin.readline
mod = 2019
def main():
    s = input().rstrip()
    n = len(s)
    d = {}
    d[0] = 1
    ten = 1
    T = 0
    for x in reversed(s):
        T += ten*int(x)
        ten *= 10
        T %= mod
        ten %= mod
        if T in d:
            d[T] += 1
        else:
            d[T] = 1

    print(sum(i*(i-1)//2 for i in d.values()))
if __name__ == "__main__":
    main()

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


l = [0] * 2019
l[0] = 1
m = 1
temp = 0
for i in range(N-1, -1, -1):
    temp += int(S[i]) * m
    temp %= 2019
    l[temp] += 1
    m *= 10
    m %= 2019

ans = 0

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

print(ans)

Solution (Python):
from collections import defaultdict

s = input()
n = len(s)
mod = 2019
DP = [0 for i in range(n+2)]
DP[n+1] = 0

num = 1
for i in reversed(range(n)):
    DP[i] = (DP[i+1] + int(s[i])*(num))%mod
    num = num*10%mod
DP.pop(-1)

arr = defaultdict(int)
for dp in DP:
    arr[dp]+=1

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

Solution (Python):
s = input()

MOD = 2019

d = [0] * MOD
d[0]=1
r=0
t=1

for i in reversed(s):
    r += int(i)*t
    r %= MOD
    t *= 10
    t %= MOD
    d[r] += 1

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

Solution (Python):
S = input()[::-1]
ans = 0
dp = [0] * 2019
dp[0] = 1
val = ''
m = 0
x_10 = 1
for s in S:
    m = (m + int(s) * x_10) % 2019
    dp[m] += 1
    x_10 = (x_10 * 10) % 2019
for i in dp:
    ans += i * (i-1) // 2
print(ans)

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

MOD = 2019
T = [1] + [0] * 2018
d, p = 0, 1
for c in reversed(s):
	d = (d + p * int(c)) % MOD
	p = p * 10 % 2019
	T[d] += 1

print(sum(x * (x - 1) // 2 for x in T))

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):
s = input()
n = len(s)
m = 2019
a = 0
r = [0 for _ in range(m+1)]
r[0] = 1
z = 0
for i in range(0,n):
    z = (int(s[n-i-1])*pow(10,i,m) + z)%m
    a += r[z]
    r[z] += 1
print(a)

Solution (Python):
s = str(input())
s=s[::-1]
mod = 2019
li = [0]*(len(s)+1)
cnt=1
for i in range(len(s)):
    li[i+1]=li[i] + int(s[i]) * cnt
    li[i+1]%=mod
    cnt*=10
    cnt%=mod
import collections
A=collections.Counter(li[1:]);ans=0
for u,v in A.items():
    ans+=v*(v-1)//2
    if u==0:
        ans+=v
print(ans)

Solution (Python):
S = input()
count = 0
l = [0] * 2019 
l[0] = 1
mod = 2019
tmp = 0

for i in range(1, len(S) + 1):
    tmp = (tmp + int(S[len(S) - i]) * pow(10, i - 1, mod)) % mod
    
    l[tmp] += 1


for j in range(2019):
    if l[j] >= 2:
        count += l[j] * (l[j] - 1) // 2

print(count)

Solution (Python):
from collections import defaultdict

S = input()

D = defaultdict(int)
D[0] += 1
x = 0
d = 1
for s in reversed(S):
  x = (x + int(s) * d) % 2019
  D[x] += 1
  d = (d * 10) % 2019

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

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

    p = 2019  
    s = S[::-1]
    u = [0] * len(S)
    u[0] = s[0] % p

    power = 1
    for i in range(1, len(S)):
        power *= 10
        power %= p
        u[i] = u[i - 1] + power * s[i]
        u[i] %= p
    count = Counter(u)
    return sum(v * (v - 1) // 2 for v in count.values()) + count[0]

print(d_multiple_of_2019())

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

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

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

print(ans)

Solution (Python):
s = str(input())
ans = [0]*2020
a = 0
po = 0
aaa = 0
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

for i in range(len(s)):
    a += int(s[len(s)-i-1]) * power_func(10,po,2019)
    a = a % 2019
    ans[a] += 1
    po += 1
    if a == 0:
        aaa += 1
for i in range(2020):
    aaa += ans[i] * (ans[i]-1)//2
print(aaa)

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):
s=input()
t=len(s)
ans=0
ruiseki=[int(s[-1]) for i in range(t)]
for i in range(1,t):
    ruiseki[i]=(ruiseki[i-1]+int(s[-1-i])*pow(10,i,2019))%2019
from collections import Counter
ans+=ruiseki.count(0)
C=Counter(ruiseki)
for x in C.values():
    ans+=x*(x-1)//2
print(ans)

Solution (Python):
from collections import defaultdict

s = input()
n = len(s)
mod = 2019
DP = [0 for i in range(n+2)]
DP[n+1] = 0

for i in reversed(range(n)):
    DP[i] = (DP[i+1] + int(s[i])*(pow(10,n-i-1,mod)))%mod
DP.pop(-1)

arr = defaultdict(int)
for dp in DP:
    arr[dp]+=1

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

Solution (Python):
from collections import defaultdict

S = tuple(map(int, list(input())))
MOD = 2019

d = defaultdict(int)
d[0] = 1

tmp = 0
for i, s in enumerate(reversed(S)):
    tmp = (tmp + s * pow(10, i, MOD)) % MOD
    d[tmp] += 1
print(sum(v * (v - 1) // 2 for v in d.values()))

Solution (Python):
from sys import stdin
s = stdin.readline().rstrip()
n = len(s)
dic = {}
dic[0] = 1
now = 0
mul = 1
for i in range(n-1,-1,-1):
    now = (now+(10*mul)*int(s[i]))%2019
    if now in dic:
        dic[now] += 1
    else:
        dic[now] = 1
    mul *= 10
    mul %= 2019
print(sum(dic[i]*(dic[i]-1)//2 for i in dic))

Solution (Python):
s=input()[::-1]
ans=0
u=0
d=1
l=[0]*2019
l[0]=1
for i in map(int,s):
  u=(u+i*d)%2019
  l[u]+=1
  d=d*10%2019
for i in l:
  ans+=i*(i-1)//2
print(ans)

Solution (Python):
s = input()
ans = 0
tmp = 0
mods = [0]*2019
mods[0] = 1
order = 1
for i in reversed(s):
    tmp += int(i) * order
    mods[tmp % 2019] += 1
    order *= 10
    order %= 2019
ans = sum(n*(n-1)//2 for n in mods)
print(int(ans))

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

D=defaultdict(int)
D[0]=1
ans=0
prev=0

for i,s in enumerate(reversed(S)):
    cur=(prev+pow(10,i,2019)*int(s))%2019
    ans+=D[cur]
    D[cur]+=1
    prev=cur
print(ans)

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

num_rem = [0] * p
t = 1
mod = 0
num_rem[mod] = 1
for i in range(n):
    mod = (mod + int(s[-i-1])*t)%p
    num_rem[mod] += 1
    t = (10*t)%p
for m in num_rem:
    ans += (m*(m-1))//2
print(ans)

Solution (Python):






"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple


def solve(s: str) -> int:
    modulo = 2019
    remainders = defaultdict(int, {0: 1})
    power = 1
    curr = 0
    LOG.debug((s))
    result = 0
    for i in range(len(s) - 1, -1, -1):
        c = int(s[i])
        curr = (power * int(c) + curr) % modulo
        power = (power * 10) % modulo
        result += remainders[curr]
        remainders[curr] += 1
    LOG.debug((remainders))
    return result


def do_job():
    "Do the work"
    LOG.debug("Start working")
    
    S = input()
    
    
    
    
    result = solve(S)
    print(result)


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case 
    
    


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None

if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            
            
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Solution (Python):
s = input()

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

amari = 0
tmp = 1
for i in range(1, len(s)+1):
    amari = (amari + int(s[-i])*tmp) % 2019
    lst[amari] += 1
    tmp = (tmp*10) % 2019

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

print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(300000)


def solve(S: str):
    s = [0] * 2019
    s[0] = 1
    ret = 0
    for c in S:
        cc = int(c)
        n = [0] * 2019
        for k, v in enumerate(s):
            kk = (k * 10 + cc) % 2019
            n[kk] += v
            if kk == 0:
                ret += v
        s = n
        n[0] += 1
    print(ret)
    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):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    s = S()
    d = defaultdict(int)
    tmp = 0
    ans = 0
    d[0] = 1
    for i, si in enumerate(s[::-1]):
        tmp += int(si) * pow(10, i, 2019)
        tmp %= 2019
        ans += d[tmp]
        d[tmp] += 1
    print(ans)
    return



if __name__ == '__main__':
    solve()

Solution (Python):
import collections
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


s=list(input())
s=s+[0]
mod=0
ans=[]
count=0
n=len(s)
p=2019

for i in range(n):
    mod+=(pow(10,i,p)*int(s[n-i-1]))%p
    mod%=p
    ans.append(mod)

ans = collections.Counter(ans)
ans=ans.most_common()
for i in range(len(ans)):
    if ans[i][1]>=2:
        count+=combinations_count(ans[i][1],2)

print(count)

Solution (Python):
s=list(input())
s=[int(i) for i in s]
now=0
c=[0]*2019
c[0]=1
for n,i in enumerate(s[::-1]):
    now+=i*pow(10,n,2019)
    c[now%2019]+=1
ans=0
for k in range(2019):
    ans+=c[k]*(c[k]-1)//2
print(ans)

Solution (Python):
s=list(map(int,list(input())))[::-1]
n=len(s)
chk=[0]*2019
chk[0]=1
t,m,ans=1,0,0
for i in s:
    m=(m+t*i)%2019
    ans+=chk[m]
    chk[m]+=1
    t=t*10%2019
print(ans)

Solution (Python):
M = 2019
dp = [0] * M
s = input()
x = 0
for c in s:
    c = int(c)
    dp2 = [0] * M
    for j in range(M):
        index = (j*10 + c) % M
        dp2[index] += dp[j]
    dp = dp2
    dp[c] += 1
    x += dp[0]
print(x)

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

Solution (Python):
from sys import stdin

S = stdin.readline().rstrip()
N = len(S)
Sp = S

res_map = [0 for _ in range(N)]

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

res_map[N-1] = int(S[N-1])
index=1


for i in range(N-2,-1,-1):
    res_map[i] = (int(S[i])*aa_list2[index] + res_map[i+1])%2019
    index+=1

aa_table = [0 for i in range(2019)]
for i in range(len(res_map)):
    aa_table[res_map[i]]+=1

aa_table[0]+=1

tot = 0
for i in range(2019):
    tot+=int((aa_table[i]-1)*aa_table[i]/2)

print(tot)

Solution (Python):
def main(S=None):
    if not S:
        S = input()
    r = [0]*2019
    r[0] = 1
    tmp = 0
    base = 1
    for s in S[::-1]:
        s = int(s) * base
        base *= 10
        base %= 2019
        tmp += s
        tmp %= 2019
        r[tmp] += 1
    count = 0
    for v in r:
        count += v*(v-1)//2
    print(count)
    return count


if __name__ == "__main__":
    
    
    
    main()

Solution (Python):
s=input()
ans=0
u=0
l=[0]*2019
l[0]=1
for i,n in enumerate(map(int,s)):
  u=(u+n*pow(10,len(s)-i,2019))%2019
  l[u]+=1
for i in l:
  ans+=i*(i-1)//2
print(ans)

Solution (Python):
from collections import Counter

M = 2019

Ss = input().rstrip()

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

As.reverse()


cnt = Counter(As)

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

print(ans)

Solution (Python):
def main():
    MOD=2019
    S=input()[::-1]
    count=[1]+[0]*MOD
    r,tmp=0,1
    for i in S:
        r += int(i)*tmp
        r %= MOD
        tmp *= 10
        tmp %= MOD
        count[r] += 1

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

main()

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()
n = len(s)
p = 0
ten = 1
cnt = [0] * 2019
cnt[0] = 1
ans = 0
for i in reversed(s):
    p = (p + int(i) * ten) % 2019
    ans += cnt[p]
    cnt[p] += 1
    ten = ten * 10 % 2019

print(ans)

Solution (Python):
S = input()
if len(S) < 4:
    print(0)
    exit(0)
dp = [0]*2019
dp[0] = 1
s = int(S[-1])
dp[s] = 1
ans = 0
for k in range(len(S)-2,-1,-1):
    s = int(S[k])*(pow(10,len(S)-k-1,2019)) + s
    s %= 2019
    dp[s] += 1
for e in dp:
    ans += e*(e-1)//2
print(ans)

Solution (Python):
a = [int(c) * pow(10, i, 2019) % 2019 for i, c in enumerate(reversed(input()))]
s = [0]
for x in a:
  s += [(s[-1] + x) % 2019]
cnt, ans = [0] * 2019, 0
for x in s:
  ans += cnt[x]
  cnt[x] += 1
print(ans)

Solution (Python):
S = input()
MOD =2019
count = [0]*MOD
r = 0
t = 1
for i in reversed(S):
    r += int(i) * t
    r %= MOD
    t *= 10
    t %= MOD
    count[r] += 1

count[0] += 1
print(int(sum(i*(i-1)/2 for i in count)))

Solution (Python):

s = input()[::-1]
n = len(s)
cs = [0] * (n + 1)
ten = 1
for i in range(n):
    cs[i + 1] = int(s[i]) * ten % 2019
    ten = ten * 10 % 2019
for i in range(n):
    cs[i + 1] = (cs[i + 1] + cs[i]) % 2019
cnt = [0] * 2019
for i, x in enumerate(cs):
    cnt[x] += 1
ans = sum(x * (x - 1) // 2 for x in cnt)
print(ans)

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

S = list(input())
S = list(map(int, S))
mod = 2019
s = [S.pop()]
d = 1
for i in S[::-1]:
    d = (d * 10) % mod
    s.append((i * d) % mod)

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

Solution (Python):
def resolve():
    S = input()
    table=[0]*2019
    table[0]=1
    x = 0
    x_10 =1
    for i in S[::-1]:
 
        x = (x+ int(i)*x_10)%2019
 
        table[x]+=1
 
        x_10*=10
        x_10 %= 2019
 
    ans =0
    for i in table:
        ans += i*(i-1)//2
    
    print(ans)
 
 
 
if __name__ == "__main__":
    resolve()

Solution (Python):
S = [int(a) for a in input()[::-1]]
m = 2019
N = len(S)
s = 0
p = 1
X = [0] * 2019
X[0] = 1
ans = 0
for a in S:
    s = (s + a * p) % m
    ans += X[s]
    X[s] += 1
    p = p * 10 % m
 
print(ans)

Solution (Python):
import collections
s=input()
n=len(s)
a=[]
x=0
p=1
for i in range(n):
	j = n-1-i
	c = int(s[j])
	p %= 2019
	x += (p*c)%2019
	p *= 10
	x %= 2019
	a.append(x)
c=collections.Counter(a)
ans = 0
for k,v in c.items():
	if k==0:
		ans += v
	ans += v*(v-1)//2
print(ans)

Solution (Python):
import sys
import math
import queue
import copy
import bisect
from collections import deque 


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])



ss = input()























ls=len(ss)


    




kl=[0]*2019
kl[0]=1



tmp=0
t2=1
count=0
for s in reversed(ss):
    tmp=(tmp+int(s)*pow(10,count,2019))%2019
    kl[tmp]+=1
    
    count+=1
    






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