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

Solution (Python):
s = input()
s = list(reversed(s))
n = len(s)
dp1 = [0]*n
dp2 = [0]*n
counting = [0]*2019
counting[0] += 1
dp1[0] = 1
dp2[0] = int(s[0])
counting[dp2[0]] += 1
if n >= 2:
    for i in range(1,n):
        dp1[i] = (10*dp1[i-1]) % 2019
        dp2[i] = (int(s[i])*dp1[i]+dp2[i-1]) % 2019
        counting[dp2[i]] += 1

sm = 0
for j in range(2019):
    sm += int(counting[j]*(counting[j]-1)/2)
print(sm)

Solution (Python):

S = input()
mod = [1]+[0]*2018
tmp = 0
seki = 1
for k in range(len(S)):
    tmp = (seki*int(S[len(S)-1-k])+tmp)%2019
    mod[tmp] += 1
    seki = (seki*10)%2019
ans = 0
for k in range(2019):
    ans += mod[k]*(mod[k]-1)//2
print(ans)

Solution (Python):
from collections import Counter
S = input()[::-1]
cur = 0
mods = Counter()
mods[0] += 1
MOD = 2019
for i,d in enumerate(S):
  cur += int(d) * pow(10, i, MOD)
  mods[cur%MOD] += 1

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

print(res)

Solution (Python):
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
from collections import deque
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
s=input()
n=len(s)
ten=[1]
mod=2019
for i in range(n-1):
  ten.append((ten[i]*10)%mod)
modls=[0]*n
modls[n-1]=int(s[n-1])
dic=defaultdict(int)
dic[modls[n-1]]+=1
dic[0]=1
for i in range(n-2,-1,-1):
  modls[i]=int(s[i])*ten[n-1-i]+modls[i+1]
  modls[i]%=mod
  dic[modls[i]]+=1
ans=0

for num in dic.values():
	ans+=num*(num-1)//2

print(ans)

Solution (Python):
s=list(input())
mod=2019
mdict={}
mdict[0]=1
ans=0
tmp=0
for i in range(len(s)):
    n=s.pop()
    key=(int(n)*pow(10,i,mod)+tmp)%mod

    if key in mdict:
        mdict[key]+=1
    else:
        mdict[key]=1
    tmp=key

for var in mdict.values():
    ans+=var*(var-1)//2

print(ans)

Solution (Python):
s = input()[::-1]
counts = [0] * 2019
counts[0] = 1
digit = 1
sum = 0
for c in s:
  sum = (sum + int(c) * digit) % 2019
  digit = digit * 10 % 2019
  counts[sum] += 1
 
result = 0
for c in counts:
  result += c * (c - 1) // 2
 
print(result)

Solution (Python):
S = list(map(int, list(input())))
S.reverse()
a = [0]*len(S)
y = 2019
x = 1
t = 0
cnt = [0]*y
res = 0
for i in range(len(S)):
    cnt[t] += 1
    t += S[i]*x
    t %= y
    res += cnt[t]
    x = x*10%y
print(res)

Solution (Python):
import sys
import math
from collections import deque
from collections import Counter

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


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


def main():
    S = SI()
    l = len(S)
    T = [0] * (l+1)
    inv_S = S[::-1]
    for i, s in enumerate(inv_S):
        s = int(s)
        T[i+1] = (T[i] + s * pow(10, i, 2019)) % 2019
    C = Counter(Counter(T).values())
    ans = 0
    for n, x in C.items():
        if n == 1: continue
        ans += cmb(n, 2) * x
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
s = input()[::-1]
counts = [0] * 2019
counts[0] = 1
digit = 1
sum = 0
for c in s:
  sum = (sum + int(c) * digit) % 2019
  digit = digit * 10 % 2019
  counts[sum] += 1

result = 0
for c in counts:
  result += c * (c - 1) // 2

print(result)

Solution (Python):
from collections import deque
s=input()[::-1]
l=[0]*2019
ten=1
sm=0
cnt=0
l[0]=1
for i in range(len(s)):
    sm += int(s[i])*ten
    sm %= 2019
    cnt += l[sm]
    l[sm] += 1
    ten = ten *10 %2019
print(cnt)

Solution (Python):
from collections import Counter
MOD = 2019
S = input()
T = [0]
base = 1
for si in reversed(S):
    T += [(T[-1] + int(si) * base) % MOD]
    base = (base * 10) % MOD
ans = 0
for n, count in Counter(T).items():
    ans += count*(count-1)//2
print(ans)

Solution (Python):
from collections import deque
s  = input()[::-1]
lsts = [0] * 2019
kai = 1
cou = 0
st = 0
lsts[0] = 1
for i in s:
  st += int(i) * kai
  st %= 2019
  cou += lsts[st]
  lsts[st] += 1  
  kai = kai * 10 % 2019

print(cou)

Solution (Python):
S = input()[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1
current = 0
x = 1

for s in S:
    current = (current + x * int(s)) % 2019
    ans += mods[current % 2019]
    mods[current % 2019] += 1
    x = x * 10 % 2019

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

def main():
    S = [int(s) for s in input()]
    N = len(S)
    K = 2019

    V = [0] * (N+1)
    for i in reversed(range(N)):
        rev_i = (N-1)-i
        V[rev_i+1] = V[rev_i] + S[i] * (pow(10,rev_i+1,K))
        

    dic = {} 
    U = set()
    for v in V:
        u = v % K
        if u in U:
            dic[u] += 1
        else:
            dic[u] = 1
            U.add(u)

    ans = 0
    for u in U:
        u_count = dic[u]
        ans += u_count * (u_count-1) // 2

    
    
    
    print(ans)

if __name__ == "__main__":
  main()

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

x = []
y = 0

while 10 ** y % 2019 not in x:
    x.append(10 ** y % 2019)
    y += 1

z = len(x)

m = [0 for i in range(2019)]
m[0] = 1
a = 0
for i in reversed(range(0, t)):
    a += x[(t-i-1) % z] * (int(s[i]) % 2019)
    a = a % 2019
    m[a] += 1

def triangle(n):
    if n > 1:
        return n * (n-1) // 2
    else:
        return 0

p = list(map(triangle, m))

print(sum(p))

Solution (Python):
MAX = 600000
MOD = int(1e9) + 7
fac = [0] * MAX
ifac = [0] * MAX
fac[0] = 1
for i in range(1,MAX):
    fac[i] = (fac[i-1] * i) % MOD
ifac[MAX-1] = pow(fac[MAX-1],MOD-2,MOD)
for i in reversed(range(1,MAX)):
    ifac[i-1] = (ifac[i] * i) % MOD

def combinations(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return (fac[n] * ifac[k] * ifac[n-k]) % MOD
MOD2 = 2019
s = list(input())
s.reverse()
n = len(s)
ans = 0
lis = [0] * 2020
x = 1
cnt = 0
lis[cnt] += 1
for i in s:
    cnt += int(i) * x
    cnt %= MOD2
    lis[cnt] += 1

    x *= 10
    x %= MOD2





for i in lis:
    ans += combinations(i,2)

print(ans)

Solution (Python):
MOD = 2019
s = list(input())
s.reverse()
n = len(s)
lis = [0] * 2020
ans = 0
x = 1
tot = 0
for i in range(n):
    lis[tot] += 1
    tot += int(s[i]) * x
    tot %= MOD
    ans += lis[tot]
    x *= 10
    x %= MOD
print(ans)

Solution (Python):
S = input()
from collections import defaultdict
d = defaultdict(int)
before = 0
for i in range(1,len(S)+1):
    now = (int(S[-i])*pow(10,i,2019)+before) % 2019
    d[now] += 1
    before = now
d[0] += 1
ans = 0
for i in d.values():
    ans += i*(i-1)//2
print(ans)

Solution (Python):
from collections import Counter


def main():
    MOD = 2019
    s = input()
    n = len(s)
    t = [0] * (n + 1)
    
    for i in range(n - 1, -1, -1):
        t[i] = t[i + 1] + pow(10, n - i - 1, MOD) * int(s[i])
        t[i] %= MOD
    c = Counter(t)
    cnt = 0
    for v in c.values():
        cnt += v * (v - 1) // 2
    print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
from numba import jit
@jit(nopython=True)
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()
s = S[::-1]

cnt = [0]*2019
cnt[0] = 1
number = 0
d = 1

for i in s:
  number += int(i)*d
  cnt[number % 2019] += 1
  d *= 10
  d = d % 2019

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

print(ans)

Solution (Python):
import sys
import itertools

import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

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

n = input()
n = reversed(n)

x = 1
count = [0 for _ in range(2019)]
MOD = 2019
acc = 0
count[0] = 1
ans = 0

for c in n:
    a = x * int(c)
    acc += a
    acc %= MOD
    ans += count[acc]
    count[acc] += 1
    x = (x * 10) % MOD

print(ans)

Solution (Python):

from collections import Counter

def main():
    S = input()
    N = len(S)
    T = [0] * (N+1)
    
    for i in range(N-1,-1,-1):
        T[i] = (T[i+1] + int(S[i]) * pow(10,N-i,2019)) % 2019
    l = Counter(T)
    ans = 0
    for v in l.values():
        ans += v * (v-1) // 2
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
s=input()
n=len(s)
s=s[::-1]
from collections import Counter
c=Counter()
m=0
c[m]+=1
d=1
for i in range(n):
  m+=int(s[i])*d
  m%=2019
  d*=10
  d%=2019
  c[m]+=1

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

Solution (Python):
from sys import stdin, stdout
s = input()
n = len(s)


if len(s) <= 3:
    print(0)
    exit()

suffix_rems = [-1]*n
suffix_rems[-1] = int(s[-1])
suffix_rems[-2] = int(s[-2:])
suffix_rems[-3] = int(s[-3:])

rems_d = dict()
rems_d[0] = 1
rems_d[int(s[-1])] = 1
rems_d[int(s[-2:])] = 1
rems_d[int(s[-3:])] = 1

special_keys = set()
for i in range(n-3)[::-1]:
    rem = (pow(10, n-i-1, 2019) * int(s[i]) + suffix_rems[i + 1])%2019

    if rem in rems_d:
        rems_d[rem] += 1
        special_keys.add(rem)
    else:
        rems_d[rem] = 1

    suffix_rems[i] = rem

ans = 0
for key in special_keys:
    t = rems_d[key]
    ans += (t*(t-1))//2

print(ans)

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

cnt = [0 for _ in range(2019)]
S = S[::-1]
wk = 0
cnt[0] = 1

for i in range(0,N):
  wk = (wk + int(S[i]) * pow(10,i,mod)) % mod
  
  cnt[wk] += 1
  
ans = 0
for i in range(2019):
  m = cnt[i]
  ans += m * (m-1) // 2
  
print(ans)

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

cnt = [0 for _ in range(2019)]
S = S[::-1]
wk = 0
cnt[0] = 1

for i in range(0,N):
  wk = (wk + int(S[i]) * pow(10,i,mod)) % mod
  
  cnt[wk] += 1
  
ans = 0
for i in range(2019):
  m = cnt[i]
  ans += m * (m-1) // 2
  
print(ans)

Solution (Python):
from collections import Counter
s=input()[::-1]
DP=[0]

num,point=0,1
for i in s:
    num +=int(i)*point
    num %=2019
    DP.append(num)
    point *=10
    point %=2019

ans=0
DP=Counter(DP)
for v,m in DP.items():
    if m>=2:
        ans +=m*(m-1)//2
print(ans)

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


MOD = 2019
S = sr()
remain = [0] * 2019
remain[0] = 1
answer = 0
power = 1
cur = 0
for s in S[::-1]:
    num = int(s)
    cur += num * power
    cur %= MOD
    answer += remain[cur]
    remain[cur] += 1
    power *= 10; power %= MOD

print(answer)

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
import numpy as np

Mod = 1000000007
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  
    s = input()
    n = len(s)
    fac = 1
    cur = 0
    value = [0] * 2019
    value[0] += 1
    for i in range(n):
        add = int(s[n - 1 - i])
        cur = (cur + fac * add) % 2019
        fac = (fac * 10) % 2019
        value[cur] += 1
    ans = 0
    for i in range(2019):
        ans += value[i] * (value[i] - 1) // 2
        
    print(ans)

if __name__ == "__main__":
    main()

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

def resolve():
    S = input()

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

    
    rmd = 0
    num_rate = 1
    L = len(S)
    for i in range(L):
        rmd = (int(S[L-i-1])*num_rate + rmd) % 2019
        num_rate = num_rate*10%2019
        cnt[rmd] += 1

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

if __name__ == '__main__':
    resolve()

Solution (Python):
def main():
    s = map(int, input()[::-1])
    mod = 2019
    counts = [0] * mod
    counts[0] = 1
    t = 0
    x = 1
    for num in s:
        t = (t + num * x) % mod
        counts[t] += 1
        x = (x * 10) % mod
    ans = 0
    for count in counts:
        if count > 1:
            ans += count * (count - 1) // 2
    print(ans)


main()

Solution (Python):
from collections import defaultdict
S=input()
D=defaultdict(int)
D[0]=1
n=0
i=0
a=[0]*len(S)
b=1
for s in S[::-1]:
  n+=int(s)*b
  a[i]=n%2019
  i+=1
  b=(b*10)%2019


for i in range(len(a)):
  D[a[i]]+=1

ans=sum([i*(i-1)//2 for i in D.values()])
print(ans)

Solution (Python):
from collections import defaultdict

S = list(input())
S = [int(i) for i in S]
D = defaultdict(int)
mod = 2019

N = len(S)
Mlis = [0]*N
Mlis[-1] = S[-1] % mod

for i in range(N-2, -1, -1):
  Mlis[i] = (Mlis[i+1] + pow(10, N-1-i, mod) * S[i]) % mod

for i in Mlis:
  D[i] += 1

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

print(ans)

Solution (Python):
s = list(map(int, list(input())))

mod = 2019

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

num = 0

pow10mod = 1

for i in range(len(s)):
    num = (num + s[-(i+1)] * pow10mod) % mod
    mods[num] += 1
    pow10mod = pow10mod * 10 % mod

ans = 0

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


print(int(ans))

Solution (Python):
S = input()
ans = 0
nd = 1
mod1 = 0
listmod = [0]*2019
for i in S[::-1]:
    mod1 = (int(i)*nd + mod1)%2019
    listmod[mod1] += 1
    nd = (nd*10)%2019
for i in range(2019):
    n = listmod[i]
    if(i == 0):
        if(n == 1):
            ans += 1
        elif(n >= 2):
            ans += ((n+1)*n)//2
    else:
        if(n > 1):
            ans += ((n-1)*n)//2
print(ans)

Solution (Python):
def cal(S):
    N = len(S)
    num,cnt = 0,0
    mod = 2019
    rem_dict,rem_set = {},set()
    for i in range(N):
        num = (num + int(S[N-1-i]) * pow(10,i,mod)) % mod
        if num in rem_set:
            rem_dict[num] += 1
        else:
            rem_set.add(num)
            rem_dict[num] = 1

    if 0 in rem_set:
        output = rem_dict[0] * (rem_dict[0] + 1) // 2
    else:
        output = 0
    rem_set.discard(0)
    for rem in rem_set:
        output += rem_dict[rem] * (rem_dict[rem]-1) // 2

    return output

def main():
    S = input()

    print(cal(S))

if __name__ == "__main__":
    main()

Solution (Python):
def cal(S):
    N = len(S)
    num,cnt = 0,0
    mod = 2019
    rem = [0 for _ in range(mod)]
    for i in range(N):
        num = (num + int(S[N-1-i]) * pow(10,i,mod)) % mod
        rem[num] += 1

    output = rem[0] * (rem[0] + 1) // 2
    for i in range(1,mod):
        output += rem[i] * (rem[i]-1) // 2

    return output

def main():
    S = input()

    print(cal(S))

if __name__ == "__main__":
    main()

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)
res = 0
for v in C.values():
  res += v*(v-1) // 2

print(res)

Solution (Python):
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    s=STR()
    cnt=[0]*2019
    cnt[0]=1
    temp=0
    keta=1
    ans=0
    for i in s[::-1]:
        temp=(temp+int(i)*keta)%2019
        keta=(keta*10)%2019
        cnt[temp]+=1
    for i in cnt:
        ans+=(i*(i-1))//2
    print(ans)
    
    
if __name__ == '__main__':
    do()

Solution (Python):
import sys

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

N = 2019
L = len(S)
curr = 0
seen = {}
INV = 210
seen[curr] = 1
for i in range(L):
    curr = (curr * 10 + int(S[i])) % N
    t = (curr * pow(10, L-i, N)) %N
    if t not in seen: seen[t] = 0
    seen[t] += 1

res = 0
for i in range(N):
    if i not in seen: continue
    t = seen[i]
    res += t * (t-1)//2
print(res)

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

digit = 1
counts = [0] * 2019
counts[0] = 1
current = 0
for s in S[::-1]:
  current = (current + int(s) * digit) % MOD
  counts[current] += 1
  digit = (digit * 10) % MOD
  
ans = 0
for c in counts:
  ans += c * (c-1) // 2
  
print(ans)

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

counts = [0]*2019

counts[0] = 1
 
num, d = 0, 1
 
for c in S:
  
  num += int(c) * 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 math

import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    s = list(map(int,input()))[::-1]
    d = defaultdict(int)
    ans = 0
    ni = 0
    mod = 2019
    d[0] = 1
    n10 = 1
    for i in s:
        ni = (ni+i*n10)%mod
        d[ni] += 1
        n10 = (n10*10)%mod
    for i in d.values():
        ans += i*(i-1)//2
    print(ans)

    return

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

def main():
    s = input()
    n = len(s)
    ans = 0
    num = 0
    pow10 = 1
    d = defaultdict(int)
    d[0] = 1
    for i in reversed(range(n)):
        
        pow10 = pow10 * 10 % 2019
        num += int(s[i]) * pow10
        mod = num % 2019
        ans += d[mod]
        d[mod] += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
import numpy as np
def main():
    s = input()
    n = len(s)
    d = np.zeros(2019,np.int64)
    ans = 0
    num = 0
    pow10 = 1
    d[0] = 1
    for i in reversed(range(n)):
        pow10 = pow10 * 10 % 2019
        num += int(s[i]) * pow10
        
        mod = num % 2019
        ans += d[mod]
        d[mod] += 1
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
S = list(input())
N = len(S)
num = 0
cnt = [0]*2019
cnt[0] = 1
d = 1

for i in range(N-1, -1, -1):
    num += int(S[i]) * d
    num %= 2019
    
    cnt[num] += 1
    d *= 10
    d %= 2019

ans = 0
for c in cnt:
    ans += c * (c-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):
def solve(s, p=2019):
    s = s[::-1]
    memo = [0] * p
    memo[0] = 1
    ans = 0
    q = 0
    r = 1
    for c in s:
        q = (q + int(c)*r) % p
        ans += memo[q]
        r = 10*r % p
        memo[q] += 1
    return ans

s = input()
print(solve(s))

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

Solution (Python):
import numpy as np
S=input()
N=len(S)
mod=[0 for i in range(2019)]
mod2=0
ten=1
for i in range(N-1,-1,-1): 
  s=int(S[i])*ten
  mod2+=np.mod(s,2019)
  mod2=np.mod(mod2,2019)
  mod[mod2]+=1
  ten=(ten*10)%2019
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=k*(k-1)//2+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=k*(k-1)//2
print(ans)

Solution (Python):
s = (input()[::-1]) 
n = len(s)
counts = [0]*2019
counts[0]=1
b = 1
num = 0
for i in s:
    num += int(i)*b
    num %=2019
    b *=10
    b %=2019
    counts[num]+=1


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


print(int(ans))

Solution (Python):
s = input()[::-1]
l = [0 for i in range(2019)]
l[0] = 1
a, b = 0, 1
ans = 0
for i in s:
    a += int(i) * b
    a %= 2019
    b *= 10
    b %= 2019
    l[a] += 1
for i in l:
    ans += i * (i - 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):
from collections import defaultdict
s = input()
n = len(s)
target = 2019
res = 0
dic = defaultdict(int)
dic[0] = 1
s = s[::-1]
num, d = 0, 1
for char in s:
    num += int(char) * d
    num %= target
    d *= 10
    d %= target
    dic[num] += 1
for i in dic.values():
    res += i * (i -1) //2
print(res)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    S = input()[::-1] 
    counts = [0] * 2019
    counts[0] = 1
    num, d = 0, 1

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

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

    
if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter
s=input()
n=len(s)
MOD=2019
L=[0]
for i in range(n):
    l=(int(s[n-1-i])*pow(10,i,MOD)+L[i])%MOD
    L.append(l)
LC=Counter(L)
r=0
for v in LC.values():
    r+=v*(v-1)//2
print(r)

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

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

mod = [1] + [0] * 2018
ans = 0
for i in num:
    ans += mod[i]
    mod[i] += 1
print(ans)

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

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

mod = [1] + [0] * 2018
ans = 0
for i in num:
    ans += mod[i]
    mod[i] += 1
print(ans)

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

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

mod = [1] + [0] * 2018
ans = 0
for i in num:
    ans += mod[i]
    mod[i] += 1
print(ans)

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

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

mod = [1] + [0] * 2018
ans = 0
for i in num:
    m = i % 2019
    ans += mod[m]
    mod[m] += 1
print(ans)

Solution (Python):
s=[int(_) for _ in input()]

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

d=0
m[d]+=1
p=1
for i in range(len(s)):
  d=(d+s[-i-1]*p)%2019
  m[d]+=1
  p=(p*10)%2019
  


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

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


MOD=2019
ls_rem_a=[]
d=1
for i in range(len(S)):
  ls_rem_a.append(int(S[i])*d%MOD)
  d = d*10%MOD


ls_rem_s=[0]
sum=0
for i in range(len(S)):
  sum+=ls_rem_a[i]
  sum%=MOD
  ls_rem_s.append(sum)


from collections import Counter
C_rem = Counter(ls_rem_s)
ans=0
for i in C_rem.keys():
  n=C_rem[i]
  ans+=n*(n-1)//2
print(ans)

Solution (Python):
from collections import Counter
s=input()
n=len(s)
M=[0]
mod=2019
for i in range(n):
	m=(M[-1]+int(s[n-1-i])%mod*pow(10,i,mod))%mod
	M.append(m)
MC=Counter(M)
r=0
for v in MC.values():
	if v>1:
		r+=v*(v-1)//2
print(r)

Solution (Python):
from collections import Counter
s=input()
n=len(s)
M=[0]
mod=2019
for i in range(n):
	m=(M[-1]+int(s[n-1-i])%mod*pow(10,i,mod))%mod
	M.append(m)
MC=Counter(M)
r=0
for v in MC.values():
	if v>1:
		r+=v*(v-1)//2
print(r)

Solution (Python):


def solve():
    MOD = 2019
    S = input()

    """解説AC"""
    
    As = []
    d = 1
    for moji in S[::-1]:
        a = (int(moji)*d)%MOD
        As.append(a)
        d = (d*10)%MOD

    
    ruiseki = [0]
    for i, a in enumerate(As):
        r = (ruiseki[i] + a)%MOD
        ruiseki.append(r)

    
    ruiseki_dic = {}  
    ans = 0
    for r in ruiseki:
        if not r in ruiseki_dic:
            ruiseki_dic[r] = 1
        else:
            ans += ruiseki_dic[r]
            ruiseki_dic[r] += 1

    print(ans)


def solve2():
    MOD = 2019
    S = input()

    """解説AC"""
    
    As = []
    d = 1
    for moji in S[::-1]:
        a = (int(moji)*d)%MOD
        As.append(a)
        d = (d*10)%MOD

    
    ruiseki = [0]
    for i, a in enumerate(As):
        r = (ruiseki[i] + a)%MOD
        ruiseki.append(r)

    
    
    ruiseki_dic = {}
    ans = 0
    for r in ruiseki:
        if not r in ruiseki_dic:
            ruiseki_dic[r] = 0
        ruiseki_dic[r] += 1

    def combination_formula(n, r):
        """nCrは、O(min(n-r, r))で実装する
        Notes:
            分子と分母がかなり大きな値になった場合、計算は遅くなるので注意
            求める値がmodをとった値でいい場合、フェルマーの小定理を使った方法が速い。
        """
        if n < r: return 0

        r = min(n-r, r)
        bunsi, bunbo = 1, 1
        for i in range(r):
            bunsi = bunsi*(n-i)
            bunbo = bunbo*(i+1)
        return bunsi//bunbo

    ans = 0
    for v in ruiseki_dic.values():
        if v < 2: continue
        ans += combination_formula(v,2)

    print(ans)


if __name__ == "__main__":
    solve2()

Solution (Python):


def solve():
    MOD = 2019
    S = input()

    """解説AC"""
    
    As = []
    d = 1
    for moji in S[::-1]:
        a = (int(moji)*d)%MOD
        As.append(a)
        d = (d*10)%MOD

    
    ruiseki = [0]
    for i, a in enumerate(As):
        r = (ruiseki[i] + a)%MOD
        ruiseki.append(r)

    
    ruiseki_dic = {}  
    ans = 0
    for r in ruiseki:
        if not r in ruiseki_dic:
            ruiseki_dic[r] = 1
        else:
            ans += ruiseki_dic[r]
            ruiseki_dic[r] += 1

    print(ans)



if __name__ == "__main__":
    solve()

Solution (Python):
s = input()
mod = 2019
digit = 1
mstack = 0
l = [0]*mod
l[0] = 1
ans = 0

for i in s[::-1]:
    mstack += int(i)*digit
    mstack %= mod
    l[mstack] += 1

    digit *= 10
    digit %= mod

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

print(ans)

Solution (Python):
import sys

s = sys.stdin.buffer.readline().rstrip().decode()
MOD = 2019
ans = [1] + [0 for i in range(MOD)]
t = 1
r = 0
for i in reversed(s):
    r = (r + int(i)*t) % MOD
    t = t*10%2019
    ans[r] += 1
print(sum([m*(m-1)//2 for m in ans]))

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

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

Solution (Python):
S = list(input())[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1  
current = 0
x = 1
for s in S:
    current = (current + x * int(s)) % 2019
    ans += mods[current]
    mods[current] += 1
    x = x * 10 % 2019

print(ans)

Solution (Python):
s = input()
modl = [0]*2019
modl[0] = 1
mstack = 0
digit = 1
ans = 0

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

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

print(ans)

Solution (Python):
s = input()
modl = [0]*2019
modl[0] = 1
mstack = 0
digit = 1
ans = 0

for i in range(1, len(s) + 1):
    mstack += int(s[-i]) * digit
    mstack %= 2019
    modl[mstack] += 1
    digit = digit*10%2019

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

print(ans)

Solution (Python):
S = input()
Sliststr = list(S)
Slist = [int(s) for s in Sliststr]
Smod = [0]
mod10 = [1]
count = [0]*2019
ans = 0
for i in range(len(S)-1):
  mod10.append(mod10[i]*10%2019)
for i in range(len(S)):
  Smod.append((Smod[i]+Slist[-i-1]*mod10[i])%2019)
for i in range(len(Smod)):
  count[Smod[i]] += 1
for i in range(2019):
  ans += count[i] * (count[i]-1) // 2
print(ans)

Solution (Python):
S = input()
N = len(S)
ms = [1]
for i in range(N):
  m = ms[-1]*10%2019
  ms.append(m)
Rs = [0]
for i in range(N):
  c = int(S[N-i-1])
  R = (Rs[-1]+c*ms[i])%2019
  Rs.append(R)
NRs = {}
for R in Rs:
  if R not in NRs:
    NRs[R] = 0
  NRs[R] += 1
r = 0
for R in NRs:
  N = NRs[R]
  r += N*(N-1)//2
print(r)

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

Solution (Python):
from collections import Counter

def solve_baka(s: str):
    ans = 0
    for i in range(len(s)):
        for j in range(i+1, len(s)+1):
            if int(s[i:j]) % 2019 == 0:
                print(i, j)
                ans += 1

    return ans


def main():
    s = input()
    sr = s[::-1]
    tn = [0]

    m = 1
    for i in range(len(s)):
        tn.append((tn[i]+int(sr[i])*m) % 2019)
        m = m * 10 % 2019

    ans = 0
    for _, v in Counter(tn).items():
        if v > 1:
            ans += v * (v - 1) // 2
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
S=list(map(int,input()))
L=len(S)
M=2019
d=10

U=[]
for x in range(L):
    if x==0:
        U=[1]
    else:
        U.append((U[-1]*d)%M)
        
T=[0]
for x in range(1,L+1):
    T.append((T[-1]+S[-x]*U[x-1])%M)

D={}
for x in T:
    if x in D:
        D[x]+=1
    else:
        D[x]=1

r=0
for x in D.values():
    r+=(x*(x-1))//2

print(r)

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


MOD = 2019
dp = [0] * MOD
dp[0] += 1

rem = 0
base = 1
for i in range(n):
    d = int(s[n-i-1])
    rem = (rem + base * d) % MOD
    
    dp[rem] += 1
    base *= 10
    base %= MOD

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