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()
mod = 2019

array = []
for i in range(len(S)):
    x = (int(S[len(S)-1-i])*pow(10,i,mod))%mod
    array.append(x)
array2 = [0]
y = 0
for i in range(len(S)):
    y = (y+array[i])%mod
    array2.append(y)
array3 = [0] * 2019
ans = 0
for i in range(len(array2)):
    z = array2[i]
    ans += array3[z]
    array3[z] += 1
print(ans)

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

array = []
for i in range(len(S)):
    x = (int(S[len(S)-1-i])*pow(10,i,mod))%mod
    array.append(x)
array2 = [0]
y = 0
for i in range(len(S)):
    y = (y+array[i])%mod
    array2.append(y)
array3 = [0] * 2019
ans = 0
for i in range(len(array2)):
    z = array2[i]
    ans += array3[z]
    array3[z] += 1
print(ans)

Solution (Python):
s = input()
t = s[::-1]
n = len(s)
resid = [0] * 2019
resid[0] = 1
csum = 0
powoften = 1
for i in range(n):
    csum = (csum + int(t[i]) * powoften) % 2019
    powoften = (10 * powoften) % 2019
    resid[csum] += 1
ans = 0
for i in range(2019):
    ans += resid[i] * (resid[i] - 1) // 2
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def inp():
    return int(input())
def inps():
    return input().rstrip()
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)














mod = 2019
S = inps()
dp = [0] * len(S)
mp = {}
ten = 1
for i in range(len(S)-1, -1, -1):
    n = int(S[i])
    if i == len(S) - 1:
        dp[i] = n % mod
    else:
        ten = (ten * 10) % mod
        dp[i] = (dp[i + 1] + n * ten) % mod
    if dp[i] in mp:
        mp[dp[i]] += 1
    else:
        mp[dp[i]] = 1

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

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

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()


def summarizeList(l):
  sl=sorted(l)

  a=sl[0]
  c=1
  res=[]

  for x in sl[1:]:
    if x==a:
      c+=1
    else:
      res.append([a,c])
      a=x
      c=1
  res.append([a,c])

  return res



def main():
  s=S()
  n=len(s)

  l=[]
  mul=1
  for x in s[::-1]:
    l.append(mul*int(x)%2019)
    mul*=10
    mul%=2019

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

  sl=summarizeList(l)
  

  ans=0
  for x,c in sl:
    if x==0:
      ans+=c
    if c>1:
      ans+=c*(c-1)//2

  return ans


print(main())

Solution (Python):
S = list(map(int, list(input())))[::-1]
N = len(S)
CNT = [0]*2019
CNT[0] = 1
num = 0
d = 0
for i in range(N):
    num += S[i]*pow(10, d, 2019)
    num %= 2019
    CNT[num] += 1
    d += 1
ans = 0 
for cnt in CNT:
    ans += (cnt*(cnt - 1)) // 2
print(ans)

Solution (Python):
n = input()
p = 2019
t = 1
y = 0
c = p*[0]

for x in map(int,n[::-1]):
  y+=t*x
  y%=p
  c[y]+=1
  t*=10
  t%=p

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

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

Solution (Python):
def egcd(a, b):
    """Returns a triple (g, x, y), such that ax + by = g = gcd(a,b).
       Assumes a, b >= 0, and that at least one of them is > 0.
       Bounds on output values: |x|, |y| <= max(a, b)."""
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m) 
    if g != 1:
        return None
    else:
        return x % m

def main():
    s = input()
    n = len(s)
    h = [0]
    for i in range(n):
        h.append((h[-1] * 10 + int(s[i])) % 2019)
    p = [1]
    for i in range(n):
        p.append((p[-1] * 10) % 2019)
    lk = {0 : 1}
    cnt = 0
    for i in range(1, len(h)):
        curr = (h[i] * modinv(p[i], 2019)) % 2019
        
        if curr in lk:
            cnt += lk[curr]
            lk[curr] += 1
        else:
            lk[curr] = 1 
    print(cnt)
    
if __name__ == '__main__':
    main()

Solution (Python):
S=input()
s=int(S)
mod=2019
c=[0]*(len(S)+1)
d=[0]*2019


c[0]=0
d[0]=1
for i in range(len(S)):
  c[i+1]=(c[i]+int(S[-i-1])*pow(10,i,mod))%mod
  d[c[i+1]]+=1
  
m=0
for i in range(2019):
  m+=d[i]*(d[i]-1)//2

print(m)

Solution (Python):
from collections import defaultdict

S = input()
kTarget = 2019

mod2cnt = defaultdict(int)
mod2cnt[0] += 1

ord_z = ord('0')
res = 0
for i in range(len(S)-1, -1, -1):
    d = ord(S[i]) - ord_z
    res = (res+d*pow(10, len(S)-1-i, kTarget))%kTarget
    mod2cnt[res] += 1

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

Solution (Python):
from collections import defaultdict

S = input()
S = S[::-1]
N = len(S)
memo = defaultdict(int)
memo[0] = 1
ans = 0
rest = 0
for i in range(N):
    rest += int(S[i])*pow(10,i,2019)
    rest %= 2019
    ans += memo[rest]
    memo[rest] += 1
print(ans)

Solution (Python):

import collections as cl
import sys


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 main():
    S = input()

    mods = [0] * 2019

    ttl = 0
    pows = 1

    for i in range(len(S)-1, -1, -1):
        ttl += (int(S[i]) * pows) % 2019
        ttl %= 2019
        pows *= 10
        pows %= 2019
        mods[ttl] += 1

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

    print(int(ans))


main()

Solution (Python):
ans=0
S=input()
a=len(S)
k=0
c=dict()
mod=2019
s=1
c[0]=1
for i in range(a):
  k+=(s*int(S[a-i-1]))
  k%=mod
  s*=10
  s%=mod
  if k in c:
    c[k]+=1
  else:
    c[k]=1
for i in c:
  ans+=c[i]*(c[i]-1)//2
print(ans)

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

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

from collections import Counter

def nC2(n):
    return n * (n - 1) // 2

l = list(Counter(l).values())

ans = 0
for i in l:
    ans += nC2(i)

print(ans)

Solution (Python):
s=input()

s=s[::-1]

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

num=0
d = 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):
S = list(map(int, list(input())))

pops = 0
digi = 1
cnt = [0] * 2019
cnt[0] = 1

while S:
    s = S.pop()

    pops = (pops + s * digi) % 2019
    digi = (10 * digi) % 2019

    cnt[pops] += 1

ans = 0

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

print(ans)

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

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

D = dict()
for j in L:
    if j in D:
        D[j] += 1
    else:
        D[j] = 1
ans = 0
for k in D.values():
    ans += k * (k-1) //2

print(ans)

Solution (Python):
S = input()

mod = 2019
cnt = [0] * 2019
cur = 0  
cnt[cur] = 1
d = 1   

for s in S[::-1]:
    cur += int(s) * d
    cur %= mod
    cnt[cur] += 1
    d *= 10
    d %= mod

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

print(ans)

Solution (Python):
S=[int(i) for i in list(input())][::-1]
R={}
def dic_add(x):
    if x in R:
        R[x]+=1
    else:
        R[x]=1
def dic_check(x):
    if x in R:
        return R[x]
    else:
        return 0
def pow_k(x,n,p=10**9+7):
    if n==0:
        return 1
    K=1
    while n>1:
        if n%2!=0:
            K=(K*x)%p
        x=(x*x)%p
        n//=2
    return (K*x)%p
N=len(S)
r=0
res=0
for i in range(N):
    r=(S[i]*pow_k(10,i,2019)+r)%2019
    if not r:
        res+=1
    res+=dic_check(r)
    dic_add(r)
print(res)

Solution (Python):
s = str(input())
MOD = 2019
m = 0
digit = 1
mods = [1] + [0] * 2018
for a in s[::-1]:
    m = (m + digit * int(a)) % MOD
    mods[m] += 1
    digit = digit * 10 % MOD
ans = 0
for x in mods:
    ans += x * (x - 1) // 2
print(ans)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import defaultdict
def main():
    S_ = S()
    mod_list = defaultdict(int)
    ans = 0
    num = 0
    point = 1
    for i in S_[::-1]:
        num += int(i) * point
        mod = int(num) % 2019
        mod_list[mod] += 1
        point *= 10
        point %= 2019
    values_ = mod_list.values()
    ans += mod_list[0]
    for value in values_:
        ans += (value - 1) * value // 2

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import collections
h = collections.Counter([0])
cumul,m,ans = 0,2019,0
pt = 1
for j,u in enumerate(map(int,list(raw_input()))[::-1]):
	cumul += u * pt
	cumul %= m
	pt *= 10
	pt %= m
	ans += h[cumul]
	h[cumul]+=1
print ans

Solution (Python):
def inN():
    return int(input())
def inL():
    return list(map(int,input().split()))
def inNL(n):
    return [list(map(int,input().split())) for i in range(n)]

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

cnt += mod[0]

for i in range(2019):
    if mod[i] > 1:
        cnt += (mod[i]*(mod[i]-1))/2
        
print(int(cnt))

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    s = tuple(map(int, input()))
    lens = len(s)

    d1 = defaultdict(int)
    ss = 0
    num10 = 1
    for se in s[::-1]:
        ss += (int(se) * num10) % 2019
        ss = ss % 2019
        d1[ss] += 1
        num10 = (num10 * 10) % 2019
    r = d1[0]
    for v in d1.values():
        r += v * (v - 1) // 2
    print(r)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    s = tuple(map(int, input()))
    lens = len(s)

    d1 = defaultdict(int)
    ss = 0
    num10 = 1
    for i1 in range(1, lens+1):
        ss += (int(s[-i1]) * num10) % 2019
        ss = ss % 2019
        d1[ss] += 1
        num10 = (num10 * 10) % 2019
    r = d1[0]
    for v in d1.values():
        r += v * (v - 1) // 2
    print(r)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    s = tuple(map(int, input()))
    lens = len(s)

    d1 = defaultdict(int)
    ss = 0
    num10 = 1
    for i1 in range(1, lens+1):
        ss += (int(s[-i1]) * num10) % 2019
        ss = ss % 2019
        d1[ss] += 1
        num10 = (num10 * 10) % 2019
    r = d1[0]
    for v in d1.values():
        r += v * (v - 1) // 2
    print(r)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    s = tuple(map(int, input()))
    lens = len(s)

    d1 = defaultdict(int)
    ss = 0
    k = 1
    num10 = 1
    while k <= lens:
        ss += (int(s[-k]) * num10) % 2019
        ss = ss % 2019
        d1[ss] += 1
        k += 1
        num10 = (num10 * 10) % 2019
    r = d1[0]
    for v in d1.values():
        r += v * (v - 1) // 2
    print(r)

if __name__ == '__main__':
    main()

Solution (Python):


import numpy as np
from collections import Counter

YEAR = 2019


def solve(S: str):
    
    mod_year = np.arange(1, 10)
    mod_s = []
    for Si in map(int, reversed(S)):
        mod_s.append(mod_year[Si - 1])
        mod_year = (mod_year * 10) % YEAR
    
    
    cum_sum = 0
    cum_sums = [cum_sum]
    for x in mod_s:
        cum_sum = (cum_sum + x) % YEAR
        cum_sums.append(cum_sum)

    
    answer = 0
    for _, num in Counter(cum_sums).items():
        answer += (num * (num - 1)) // 2  
    return answer


def main():
    S = input().strip()
    answer = solve(S)
    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):


import numpy as np
from collections import Counter

YEAR = 2019


def solve(S: str):
    
    mod_year = np.arange(1, 10)
    mod_s = []
    for Si in map(int, reversed(S)):
        mod_s.append(mod_year[Si - 1])
        mod_year = (mod_year * 10) % YEAR
    
    
    cum_sum = 0
    cum_sums = [cum_sum]
    for x in mod_s:
        cum_sum = (cum_sum+x) % YEAR
        cum_sums.append(cum_sum)

    answer = 0
    for _, num in Counter(cum_sums).items():
        answer += (num * (num-1)) // 2   
    return answer


def main():
    S = input().strip()
    answer = solve(S)
    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
S = input()
N = len(S)
A = [int(S[i]) for i in range(N)]
A = A[::-1]

MOD = 2019

p10 = [1] * N
for i in range(1, N):
	p10[i] = (p10[i - 1] * 10) % MOD

for i in range(N):
	A[i] = (A[i] * p10[i]) % MOD

cumsum = [A[0]] * N
for i in range(1, N):
	cumsum[i] = (cumsum[i - 1] + A[i]) % MOD

cnt = [0] * MOD
cnt[0] = 1
for i in range(N):
	cnt[cumsum[i]] += 1

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

print(ans)

Solution (Python):

"""
Created on Mon Sep  7 00:38:11 2020

@author: liang
"""

"""
＜D - Multiple of 2019>
【方針】
a = b(mod2019) => a - b は　2019の倍数
余りが等しいグループの組み合わせの総数が解になる。
既に2019の倍数であるものは単体で成立するため、[0]のカウントを一つあげておく


＜累積和＞
【計算量削減】
大きな数を使わない　⇒　mod を使う
tmp += 7 * 100000000  => 7 * ( 2019*N + α) => 7 * α　と同じ
　　⇒　累乗(10**N) に  mod をかけると良い

100000000 + γ => (2019*N + β) + γ => β + γ と同じ
　⇒　累積和　に　mod をかけると良い
 
 for文で１文字ずつ足し算していくことで実装可能
 
 reversed() : 逆順に並べ替え
 reversed(input()) : 入力を逆順に取り出す
 
"""
S = input()

MOD = 2019 

counter = [0] * 2019
counter[0] = 1
t = 1
tmp = 0
for i in reversed(S):
    tmp += int(i)*t
    tmp %= MOD 
    t *= 10
    t %= MOD   
    
    counter[tmp] += 1

ans = sum( i*(i-1)//2 for i in counter)
print(ans)

Solution (Python):
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def combinations_count(n, r):
    if n == 1:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def main():
    S = SI()
    
    ls = []
    len_S = len(S)
    rem = 0

    for s in range(len_S-1,-1,-1):
        rem = (rem+int(S[s])* pow(10, len_S-s-1, 2019))%2019
        ls.append(rem)
    
    import collections

    cls = collections.Counter(ls)
    clsv= list(cls.values())

    ans = 0

    for p in clsv:
        ans += combinations_count(p,2)
    ans += cls[0]
    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):

"""
Created on Sun Sep  6 23:39:24 2020

@author: liang
"""


counter = [0]*2019
counter[0] = 1 

S = input()
tmp = 0
"""

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

ans = 0
for i in range(2019):
    if counter[i] >= 2:
        
        ans += counter[i]*(counter[i]-1)//2
print(ans)
"""
MOD = 2019

t = 1
for i in range(1,len(S)+1):
    tmp += int(S[-i])*t
    
    tmp %= MOD 
    t *= 10
    
    t %= MOD
    
    counter[tmp] += 1
    
print(sum(i*(i-1)//2 for i in counter))

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

p = 2019
X = [0 for _ in range(p)]
X[0] = 1

dp = X[:]
ans = 0
for i in range(N):
    v = int(S[i])
    np = X[:]
    for k in range(p):
        x = (k * 10 + v) % p
        np[x] += dp[k]
    dp = np[:]
    ans += dp[0] - 1
print(ans)

Solution (Python):
s = input()
n = len(s)
dp = [0 for _ in range(n)]
dp[-1] = int(s[-1])
cnt_dic = {}
tmp = 1
ans = 0
cnt_dic[0] = 1
cnt_dic[dp[-1]] = 1
for i in range(n-2, -1, -1):
    dp[i] = (dp[i+1] + int(s[i]) * pow(10, n-i-1, 2019)) % 2019
    if not dp[i] in cnt_dic:
        cnt_dic[dp[i]] = 0
    ans += cnt_dic[dp[i]]
    cnt_dic[dp[i]] += 1

print(ans)

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

r_list = [0] * 2019
r_list[0] = 1
num, d = 0, 1
for i in range(len(S)):
    num += d*int(s_rev[i])
    num %= 2019
    r_list[num] += 1
    d *= 10
    d %= 2019

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

print(ans)

Solution (Python):
s = input()
n = len(s)
dp = [0 for _ in range(n)]
dp[-1] = int(s[-1])
memo = 0
cnt_dic = {}
tmp = 1
ans = 0
cnt_dic[0] = 1
for i in range(n-1, -1, -1):
    memo = (memo + int(s[i]) * pow(10, n-i-1, 2019)) % 2019
    if not memo in cnt_dic:
        cnt_dic[memo] = 0
    ans += cnt_dic[memo]
    cnt_dic[memo] += 1

print(ans)

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

tmp = 0
d = 1
for i in reversed(range(len(s))):
    tmp += int(s[i]) * d
    tmp %= mod
    d *= 10
    d %= mod
    dic[tmp] += 1

ans = [i * (i-1) / 2 for i in dic]
print(int(sum(ans)))

Solution (Python):
def main():
    def modpow(x, n, mod):
        res = 1
        while n:
            if n % 2:
                res *= x % mod
            x *= x % mod
            n >>= 1
        return res

    s = input()
    s = s[::-1]
    s_len = len(s)
    mod = 2019
    d = [0] * mod
    d[0] = 1
    rev_num = 0
    
    for i in range(s_len):
        rev_num += int(s[i]) * int(modpow(10, i, mod))
        rev_num %= mod
        d[rev_num] += 1
    
    
    print(sum(i*(i-1)//2 for i in d))
 
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    s = input()
    s_len = len(s)
    mod = 2019
    d = [0] * mod
    d[0] = 1
    rev_num = 0
    t = 1
    
    for i in reversed(s):
        rev_num += int(i) * t
        rev_num %= mod
        d[rev_num] += 1
        t *= 10
        t %= mod
    
    
    print(sum(i*(i-1)//2 for i in d))
 
if __name__ == '__main__':
    main()

Solution (Python):



S=str(input())[::-1]
N=len(S)
counter=[0]*2019
counter[0]=1
ans=0
num,d=0,1
for c in S:
    num += int(c) * d
    num %= 2019
    d *= 10
    d %= 2019
    counter[num]+=1
for i in counter:
    ans += i*(i-1)//2
print(ans)

Solution (Python):
import sys

S = input()[::-1]

c = [0] * 2019
c[0] = 1

num = 0
d = 1

for a in S:
    num += int(a) * d
    num %= 2019
    d *= 10
    d %= 2019
    c[num] += 1

a = 0
for i in c:
    a += i * (i - 1) // 2

print(a)

Solution (Python):
from collections import defaultdict
S = input()
S = S[::-1]

rest = 0
ans = 0
memo = defaultdict(int)
memo[0] = 1
for i in range(len(S)):
    rest = (rest + int(S[i])*pow(10,i,2019)) %2019
    ans += memo[rest]
    memo[rest] += 1
print(ans)

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

n = len(s)
ans = 0
s.reverse()

x = 1
tot = 0
count = [0]*2019
for i in range(n):
    count[tot]+=1
    tot += int(s[i])*x
    
    tot %= 2019
    ans += count[tot]
    x = x*10%2019
print(ans)

Solution (Python):
from collections import Counter
S = input()
P = [0] * (len(S)+1)
mod = 2019
d = 1
for i in range(len(S), 0, -1):
    P[i-1] = int(S[i-1])*d + P[i]
    P[i-1] = P[i-1] % mod
    d *= 10
    d = d % mod

P = Counter(P)
ans = 0
for p in P.values():
    ans += p*(p-1)//2
print(ans)

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

ls = len(s)
t = [0]
j = 1
for i in range(ls):
    u = (int(s[ls-1-i])*j + t[-1]) % 2019
    t.append(u)
    j = (j * 10) % 2019
c = Counter(t)
k = list(c.keys())
ans = 0
for i in k:
    ans += c[i]*(c[i]-1)/2
print(int(ans))

Solution (Python):
from collections import defaultdict

S = input()

d = defaultdict(int)

d[0] += 1

mod = 0
R = 1
for i in range(len(S)):
    mod = (mod + R * int(S[len(S) - i - 1])) % 2019
    R = R * 10 % 2019
    d[mod] += 1
ans = 0
for i in d.values():
    if i > 1:
        ans += i * (i - 1) / 2

print(int(ans))

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

INF = 10**18
import bisect
import statistics
mod = 10**9+7



S = input() + "0"
mod = 2019

dp = [0]
a = 1
for i in range(len(S)-1):
    dp.append((dp[-1] + int(S[len(S)-2-i])*a%mod) % mod)
    a = (a * 10) % mod

count = Counter(dp)

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

Solution (Python):
from collections import Counter


from operator import mul
from functools import reduce

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


S = input()
div = []
s = 0
kurai = 1
for i in range(len(S) - 1, -1, -1):
    
    
    if i == len(S) - 1:
        s += int(S[i]) * kurai
    else:
        s += int(S[i]) * kurai
    kurai *= 10
    kurai %= 2019
    s %= 2019
    div.append(s)
div_cnt = Counter(div)
ans = div_cnt[0]
for l in div_cnt.values():
    if l >= 2:
        ans += l * (l-1) // 2
print(ans)

Solution (Python):
from collections import Counter
n=input()[::-1]

A=[0]
num,point=0,1
for i in n:
    num +=int(i)*point
    num %=2019
    A.append(num)
    point *=10
    point %=2019

count=Counter(A)
ans=0
for i,j in count.items():
    if j>=2:ans +=j*(j-1)//2
print(ans)

Solution (Python):
from collections import Counter
n=input()[::-1]

A=[]
num,point=0,1
for i in n:
    num +=int(i)*point
    num %=2019
    A.append(num)
    point *=10
    point %=2019

count=Counter(A)
ans=0
for i,j in count.items():
    if i==0:ans +=j*(j+1)//2
    else:ans +=j*(j-1)//2
print(ans)

Solution (Python):


from collections import Counter

s = input()

r = [0]
for d in map(int, s):
    r.append((r[-1] * 10 + d) % 2019)

e = 1
for i in range(len(r) - 1, -1, -1):
    r[i] = r[i] * e % 2019
    e = e * 10 % 2019

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

counter = Counter(r)
print(sum(choose2(counter[i]) for i in counter))

Solution (Python):
"""
dp的な発想で解けるかな？
下の桁から見る。桁を一つずつ
"""
from collections import defaultdict
S = input()
N = len(S)
S = S[::-1]

ans = 0
memo = defaultdict(int)
num = 0
memo[0] = 1
for i in range(N):
    num = (num+(pow(10,i,2019)*int(S[i]))%2019)%2019
    ans += memo[num]
    memo[num] += 1

print(ans)

Solution (Python):
S = input()
N = len(S)
 
counter = [0] * 2019
counter[0] = 1
T = 0
R = 1
for i in range(N):
    T = (T + R * int(S[N - i - 1])) % 2019
    R = 10 * R % 2019
    counter[T] += 1
 
ans = 0
for i in range(2019):
    m = counter[i]
    ans += m * (m - 1) // 2
 
print(ans)

Solution (Python):
def resolve():
    S = list(input())
    rem = [0 for _ in range(2019)]
    v = 0
    rem[0] += 1
    p = 1
    for i in range(len(S)-1, -1, -1):
        v = p*int(S[i]) + v
        v %= 2019
        rem[v] += 1
        p = (p*10)%2019

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



if '__main__' == __name__:
    resolve()

Solution (Python):
S = list(map(int, input()))
L = len(S)
mod = 2019
T = []
A = [0 for i in range(mod)]
t = 0
p = 1
for i in range(L-1, -1, -1):
  t = (t + S[i] * p) % mod
  A[t] += 1
  p = (p * 10) % mod
print(A[0] + sum([a * (a-1) // 2 for a in A]))

Solution (Python):
from collections import Counter
s=input()
n=len(s)
ans=0
arr=[0]*(n+1)
if s=='0':
    print(1)
    exit()
elif n==1:
    print(0)
    exit()
for i in reversed(range(n)):
    arr[i]=(arr[i+1]+int(s[i])*pow(10,n-i-1,2019))%2019
m=Counter(arr)
for j in m.keys():
    ans+=m[j]*(m[j]-1)//2
print(ans)

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

s = input()

@lru_cache(None)
def F(s, k):
    
    
    if k == len(s)-1:
        return int(s[k])
    ret = F(s, k+1) + int(s[k])*pow(10, len(s)-1-k, 2019)
    ret %= 2019
    return ret

a = [0]*2020
for i in range(len(s)):
    a[F(s, i)] += 1

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

print(ans)

Solution (Python):
import collections

s = input()

mod = 2019
n = len(s)
t = [0]*(n+1)
for i in range(1,n+1):
    t[i] = (t[i-1] + int(s[n-i]) * pow(10, i-1, mod)) % mod
c = collections.Counter(t)
num = c.values()
ans = 0
for i in num:
    ans += i*(i-1) // 2

print(ans)

Solution (Python):

import sys
import numpy as np

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


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


def LI():
    return list(MI())


S = ST()

cnt = np.zeros(2019)
cnt[0] = 1
res = 0
tmp = 1
for s in S[::-1]:
    res += int(s) * tmp
    res %= 2019
    cnt[res] += 1
    tmp *= 10
    tmp %= 2019

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

print(int(ans))

Solution (Python):

import sys
sys.setrecursionlimit(10**9)


INF=10**20
class Counter:
    def __init__(self):
        self.dict = {}

    def add(self,x):
        if x in self.dict: self.dict[x] += 1
        else: self.dict[x] = 1

    def decrement(self,x):
        self.dict[x] -= 1
        if self.dict[x] <= 0:
            del self.dict[x]

    def get_dict(self):
        return self.dict


def solve(S):
    N = len(S)

    v1 = [0] * (N+1)
    v1[0] = 0

    for i in range(N):
        v1[i+1] = v1[i] * 10 + int(S[i])
        v1[i+1] %= 2019

    counter = Counter()
    for i in range(N+1):
        u = v1[i] * pow(10,201900-i,2019) % 2019
        counter.add(u)

    
    ans = 0
    
    for _,count in counter.get_dict().items():
        ans += count * (count-1) // 2
    
    print(ans)

    return

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



if __name__ == "__main__":
    main()

Solution (Python):
s = input()
len_s = len(s)
s_array = [int(i) for i in s]

mod = 2019
mod_array = [0]*mod

num = 0
mod_array[0] += 1
for i in range(len_s):
    num = pow(10, i, mod) * s_array[len_s - i - 1] + num
    num %= mod
    mod_array[num] += 1

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

print(int(ans))

Solution (Python):
import collections

s=list(input())
a=[0]

s.reverse()

mod=2019

mod10=1

for i in range(len(s)):
  x=int(s[i])
  y=a[-1]
  ans=(x*mod10+y)%mod
  a.append(ans)
  mod10=(mod10*10)%mod
  
ans1=0

c = collections.Counter(a)
d=list(c.values())

for r in d:
  if r>=2:
    ans1+=(r*(r-1))//2
    
print(ans1)

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=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in S[::-1]:
  s=(s+int(i)*k)%2019
  k=(k*10)%2019
  ans+=dp[s]
  dp[s]+=1
print(ans)

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

Solution (Python):
from collections import Counter

S=input()

rlist=[0]
for i in range(len(S)):
  rlist.append((rlist[-1]+int(S[-i-1])*pow(10,i,2019))%2019)
  
c = Counter(rlist)
c[0] -= 1

def nC2(n):
  return n*(n-1)//2
  
ans = c[0]
for k in c.keys():
  if c[k] >= 2:
    ans += nC2(c[k])
    
print(ans)

Solution (Python):
import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict


MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

import numpy as np

def Main():
    s = read_str()
    dp = np.zeros(2019, dtype=np.int64)
    dp[0] = 1

    cur = 0
    digit = 1

    for i in reversed(s):
        cur = (cur + int(i) * digit) % 2019
        dp[cur] += 1
        digit = digit * 10 % 2019
    
    print(np.sum([x * (x - 1) // 2 for x in dp]))

if __name__ ==  '__main__':
    Main()

Solution (Python):
s=input()
n=len(s)
rui=[0]
juu=[1]
for i in range(n+5):
  juu.append(juu[-1]*10%2019)  
for i in range(n):
  rui.append((rui[-1]+int(s[n-1-i])*juu[i])%2019)
ama=[0]*2019
for i in range(len(rui)):
  ama[rui[i]]+=1
ans=0
def ui(n):
  return max(0,n*(n-1)//2)
for i in range(2019):
  ans+=ui(ama[i])
print(ans)

Solution (Python):
import sys

S = sys.stdin.readline().strip()
ls = len(S)

mod = 2019
S = S[::-1]

acum = [0] * (ls+1)
counter = {0: 1}
for i, s_i in enumerate(S):
    acum[i+1] = (acum[i] + int(s_i) * pow(10, i, mod)) % mod
    if acum[i+1] not in counter:
        counter[acum[i+1]] = 0
    counter[acum[i+1]] += 1



ans = 0
for value, count in counter.items():
    ans += count * (count - 1) // 2

print(ans)

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











rem2019_cnts = [0]*2019
rem2019_cnts[0] = 1
curr_rem = int(s[0])
rem2019_cnts[curr_rem] = 1
curr_10_rem = 1
ans = 0
for i,si in enumerate(s[1:]):
    sint = int(si)

    next_10_rem = (curr_10_rem*10)%2019
    next_rem = (next_10_rem*sint + curr_rem)%2019

    ans += rem2019_cnts[next_rem]
    rem2019_cnts[next_rem] += 1
    
    curr_10_rem = next_10_rem
    curr_rem = next_rem
    

print(ans)