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

Solution (Python):


import sys
input = sys.stdin.readline


S = input().rstrip()

res = 0

x = 0
p = 1
L = len(S)
MOD = 2019
reminder = [0]*2019
reminder[0] = 1
for s in reversed(S):
    """ 累積和 """
    x = (int(s)*p + x)%MOD
    p = p*10%MOD
    res += reminder[x]
    reminder[x] += 1

print(res)

Solution (Python):


import sys
input = sys.stdin.readline


S = input().rstrip()

res = 0

x = 0
p = 1
L = len(S)
MOD = 2019
reminder = [0]*2019
reminder[0] = 1
for s in reversed(S):
    """ 累積和 """
    x = (int(s)*p + x)%MOD
    p = p*10%MOD
    reminder[x] += 1

for c in reminder:
    res += c*(c-1)//2

print(res)

Solution (Python):


import sys
input = sys.stdin.readline


S = input().rstrip()

res = 0

T = [0]
x = 0
p = 1
L = len(S)
MOD = 2019
for s in reversed(S):
    """ 累積和 """
    x = (int(s)*p + x)%MOD
    p = p*10%MOD
    T.append(x)

reminder = [0]*2019
for i in range(L+1):
    reminder[T[i]%MOD] += 1

for c in reminder:
    res += c*(c-1)//2

print(res)

Solution (Python):


import sys
input = sys.stdin.readline


S = input().rstrip()

res = 0

T = [0]
x = 0
p = 1
L = len(S)
MOD = 2019
for i, s in zip(range(L),reversed(S)):
    """ 累積和 """
    x = (int(s)*p + x)%MOD
    p = p*10%MOD
    T.append(x)

reminder = [0]*2019
for i in range(L+1):
    reminder[T[i]%MOD] += 1

for c in reminder:
    res += c*(c-1)//2

print(res)

Solution (Python):


from operator import mul
from functools import reduce
from collections import defaultdict

def combination(n, r):
    if not 0 <= r <= n: return 0
    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()

res = 0

T = [0]
x = 0
L = len(S)
for i, s in zip(range(L),reversed(S)):
    """ 累積和 """
    x = (int(s)*pow(10,i,2019) + x)%2019
    T.append(x)

reminder = [0]*2019
for i in range(L+1):
    reminder[T[i]%2019] += 1

for c in reminder:
    res += combination(c,2)

print(res)

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr



def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

s = list(sr())
s.reverse()
dp = [0 for i in range(len(s)+1)]
tmod = 1
for i,c in enumerate(s):
    now = int(c)
    dp[i+1] = (dp[i]+now*tmod)%2019
    tmod = (tmod*10)%2019
ans = 0
for _,v in collections.Counter(dp).items():
    ans+=(v*(v-1)//2)
print(ans)

Solution (Python):
MOD = 2019
"""
def part_count(S):
  B = [0 for _ in range(MOD)]
  C = [0 for _ in range(MOD)]
  L = [0 for _ in range(MOD)]
  R = [0 for _ in range(MOD)]
  
  if len(S) == 1:
    s = S[0]
    B[s] = 1 
    return (B, L, R, C)
  S_L = S[:len(S)//2]
  S_R = S[len(S)//2:]
  
  B1, L1, R1, C1 = part_count(S_L)
  B2, L2, R2, C2 = part_count(S_R)
    
  for j in range(MOD):
    C[j] += C1[j] + C2[j]
    L[j] += L1[j]
    R[j] += R2[j]
    for i in range(MOD):
      B[j] += B1[i] * B2[(-i + j)%MOD]
      L[j] += B1[i] * L2[(-i + j)%MOD]
      R[j] += B2[i] * R1[(-i + j)%MOD]
      C[j] += R1[i] * L2[(-i + j)%MOD]
  
  return (B, L, R, C) 
"""

S = list(input())
S.reverse()
N = len(S)
S = [int(S[i]) for i in range(N)]
MOD = 2019

a = 1
for i in range(N): 
  S[i] *= a
  S[i] %= MOD
  a *= 10 
  a %= MOD
  


T = [0 for _ in range(N+1)]
for i in range(1,N+1):
  T[i] += S[i-1] + T[i-1]
  T[i] %= MOD



C = [0 for i in range(MOD)]  
for i in range(N+1):
  C[T[i]] += 1



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

Solution (Python):
S=list(input())
P=0
M=2019
D=[0]*M
D[0]=1
X,Y=0,1
for i in range(len(S)):
  X+=Y*int(S[-i-1])
  X%=M
  P+=D[X]
  D[X]+=1
  Y=Y*10%M
print(P)

Solution (Python):
def main():
  n, mods = 0, [1]+[0]*2019
  d = 1
  for i in reversed(input()):
    n = (n+int(i)*d)%2019
    d = d*10%2019
    mods[n] += 1
  print(sum([i*(i-1)//2 for i in mods]))
main()

Solution (Python):


from collections import Counter
S = input()
dp = [0]
mod = 2019
for i in reversed(range(len(S))):
    dp.append(dp[-1]%mod+pow(10,len(S)-i-1,mod)*int(S[i]))
    dp[-1]%=mod
count = Counter(dp)
ans = 0
for key,val in count.items():
    if val>=2:
        ans += val*(val-1)//2
print(ans)

Solution (Python):
s=input()
ls=len(s)
m=[0]*(2019)
m[0]+=1

cnt = 0
b = 0
for i in range(ls):
  a = (b + pow(10,cnt,2019)*int(s[ls - i -1])) % 2019
  m[a] += 1
  b = a
  cnt += 1

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

print(ans)

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

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

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

Solution (Python):
def main():
    s = input()
    mod = 2019
    mod_count = {i: 0 for i in range(mod)}
    now_num = 0
    base = 1
    for i in range(len(s) - 1, -1, -1):
        mod_count[now_num] += 1
        now_num += base * int(s[i])
        now_num %= mod
        base *= 10
        base %= mod
    ans = 0
    mod_count[now_num % mod] += 1
    for i in range(mod):
        ans += mod_count[i] * (mod_count[i] - 1) // 2
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import itertools

S = input()[::-1]

m = [0]*len(S)
tmp = 1
for i in range(len(S)):
    m[i] = int(S[i])*tmp%2019
    tmp = tmp*10%2019

cum = [0]+[0]*len(S)
for i in range(1,len(S)+1):
    cum[i] = (cum[i-1]+m[i-1])%2019

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

Solution (Python):
S = str(input())
li = [0] * 2019
ans = 0
li[0] = 1

d = 1
s = 0
for i in S[::-1]:
  s += int(i) * d
  s = s % 2019
  li[s] += 1
  d *= 10
  d = d % 2019
  
for l in li:
  ans += l * (l-1) // 2

print(ans)

Solution (Python):
from collections import Counter
S = input()
L = len(list(S))
dp = [0] * L
dp[0] = 1
T = [0] * L
T[0] = int(S[-1])
for i in range(1, L):
    dp[i] =  dp[i - 1] * 10
    dp[i] %= 2019
    T[i] = int(S[-(i+1)]) * dp[i] + T[i - 1]
    T[i] %= 2019
ans = 0
for k, v in Counter(T).items():
    if k == 0:
        ans += v
        ans += v * (v - 1) // 2
    else:
        ans += v * (v - 1) // 2
print(ans)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


MOD = 2019



def solve():
    S = Scanner.string()
    S = S[::-1]
    cnt = [0 for _ in range(MOD)]
    tmp = 0
    ans = 0
    x = 1
    for s in S:
        cnt[tmp] += 1
        tmp += int(s) * x
        tmp %= MOD
        x *= 10
        x %= MOD
        ans += cnt[tmp]
    print(ans)


def main():
    
    
    
    
    
    
    solve()


if __name__ == "__main__":
    main()

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

s = input().strip()[::-1]
l = [0] * mod

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

n = 0
for i, c in enumerate(s):
    n += n10[i] * int(c)
    n %= mod
    l[n] += 1

ans = 0
for i, v in enumerate(l):
    if v > 1:
        ans += v * (v - 1) // 2
    if i == 0:
        ans += v
print(ans)

Solution (Python):

import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left, bisect_right 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)

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

m = 0
last = 0
dd = 1
for i in range(N):
    m += int(S[N-i-1])*dd
    m %= MOD
    
    
    dd = (dd*10)%MOD
    d[m] += 1

cnt = 0
for i, v in d.items():
    cnt += v*(v-1)//2
print(cnt)

Solution (Python):
import collections
from math import factorial

def permutations_count(n, r):
    ''' 順列 '''
    return factorial(n) // factorial(n - r)

def combinations_count(n, r):
    ''' 組み合わせ '''
    return factorial(n) // (factorial(n - r) * factorial(r))


S = input()

lis = []
amari = 1
lis.append(int(S[-1]))

for i in range(2,len(S)+1):
    amari = (amari * 10) % 2019
    lis.append((int(S[-1*i]) * amari + lis[i-2]) % 2019)

c = collections.Counter(lis)

su = 0

for k in c:
    if c[k] > 1:
        su += combinations_count(c[k], 2)
        
        
        
su += c[0]

print(su)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]



MOD = 2019
INF = int(1e15)


def solve():
    S = Scanner.string()
    N = len(S)
    S = S[::-1]
    p = 1
    total = 0
    cnt = [0 for _ in range(MOD)]
    ans = 0
    for i in range(N):
        cnt[total] += 1
        total += int(S[i]) * p
        total %= MOD
        ans += cnt[total]
        p = p * 10 % MOD
    print(ans)


def main():
    
    
    
    
    
    
    solve()


if __name__ == "__main__":
    main()

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

from collections import Counter
c=Counter()
m=0
c[m]+=1
d=1
s=s[::-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):
S=input()
ans=0
MOD=2019
cnt=[0]*MOD
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
for c in cnt:
  ans+=c*(c-1)//2
print(ans)

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

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

ans = 0

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

Solution (Python):
S = input()
MOD = 2019
cnt = [0]*MOD
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):
from collections import defaultdict


def solve(input_s: str):
    ans = 0
    n = len(input_s)
    mod = 2019
    dp = defaultdict(int)
    cur = 0
    for i in range(n, -1, -1):
        if i == n:
            dp[0] += 1
        else:
            
            cur += pow(10, n - i - 1, 2019) * int(input_s[i]) % mod
            cur %= mod
            dp[cur] += 1
    for v in dp.values():
        if v > 1:
            ans += v * (v - 1) // 2
    return ans


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

Solution (Python):
from collections import Counter, defaultdict
a = defaultdict(int)
a[0] += 1
s = input()[::-1]
cur = 0
for i, x in enumerate(s):
    cur += (int(x)*pow(10, i, 2019))%2019
    cur %= 2019
    a[cur] += 1

def comb(a):
    return a*(a-1)//2

ans = 0
for x in a.values():
    if x >= 2:
        ans += comb(x)
print(ans)

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

def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')







def solve():
    S = list(map(int, LS()))
    S = S[::-1]
    ln = len(S)
    mod = 2019

    times = 1
    for i in range(ln):
        S[i] = S[i] * times
        times = times * 10 % mod

    R = [0] * (ln+1)
    memo = {0: 1}
    ans = 0
    for i in range(1, ln+1):
        tmp = (R[i-1] + S[i-1]) % mod
        R[i] = tmp
        cnt = memo.get(tmp, 0)
        ans = ans + cnt
        memo[tmp] = cnt + 1
    print(ans)

if __name__ == '__main__':
    solve()

Solution (Python):
s=input()


s=s[::-1]
l=[0]*2019
l[0]=1
prev=0
ans=0
mul=1

for i in range(len(s)):
  now=(int(s[i])*mul)%2019
  ans+=l[(prev+now)%2019]
  l[(prev+now)%2019]+=1
  prev=(prev+now)%2019
  mul=(mul*10)%2019

print(ans)

Solution (Python):
S = input()
mod2019 = [0]*len(S)

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

mod2019.extend([0])

answer = 0
count = [0 for _ in range(2020)]

for i in range(len(S)+1):
    answer += count[mod2019[i]]
    count[mod2019[i]] += 1
print(answer)

Solution (Python):
import sys
import itertools
import numpy as np
import time
import math
import re

sys.setrecursionlimit(10**7)

from collections import defaultdict
from collections import Counter

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

def main():
    S = input()[::-1]
    MOD = 2019
    
    X = [0]
    for i, s in enumerate(S):
        X.append((X[-1] + int(s) * pow(10, i, MOD)) % MOD)
    
    C = Counter(X)
    ans = 0
    for v in C.values():
        ans += v * (v - 1) // 2
    print(ans)




if __name__ == "__main__":
    main()
    pass

Solution (Python):
import collections
import sys
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 = collections.Counter(X)
ans = 0
for v in c.values():
    ans += v * (v - 1) // 2
print(ans)

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

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

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

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

memo = [0] * 2019
memo[0] += 1

num = 0
t = 1
for i in reversed(s):
    num += int(i) * t
    num %= 2019
    t *= 10
    t %= 2019
    memo[num] += 1

ans = 0
for p in memo:
    ans += p*(p-1)//2

print(ans)

Solution (Python):
s = input()

r = 0
dict_r = {0: 1}
r10 = 1
for i in range(len(s)):
    d = int(s[-i - 1])
    r = (r + d * r10) % 2019
    r10 = (r10 * 10) % 2019

    dict_r[r] = dict_r.get(r, 0) + 1


answer = sum(v * (v - 1) // 2 for v in dict_r.values())
print(answer)

Solution (Python):
import sys 
from collections import Counter
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 2019
S = readline().decode().rstrip()
N = len(S)
S = S[::-1]
mod_list = [0]*N
mod_list[0] = int(S[0])
power = 1
for i in range(1,N):
    power *=10
    power %= mod
    mod_list[i] = power * int(S[i]) + mod_list[i-1]
    mod_list[i] %= mod
    
mod_cnt = Counter(mod_list)
ans = sum(n*(n-1)//2 for n in mod_cnt.values()) +mod_cnt[0]
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):
from collections import Counter
s = input()
ac = [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)):
    char = s[i]
    digit = len(s) - i - 1
    ac.append((ac[-1] + (int(char) * power_func(10, digit, 2019))) % 2019)


C = Counter(ac)

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

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

MOD = 2019

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

d = 1
for c in s:
    cum += int(c) * d
    cum %= MOD
    cnt[cum] += 1
    d *= 10
    d %= MOD

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

print(ans)

Solution (Python):

S = input()[::-1]


count = [0]*2019
count[0] = 1
num = 0
d = 1
for i in S:
    num += int(i)*d
    num %= 2019
    count[num] += 1
    d *= 10
    d %= 2019

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

Solution (Python):

S = input()[::-1]


count = [0]*2019
count[0] = 1
num = 0
d = 1
for i in S:
    num += int(i)*d
    count[num % 2019] += 1
    d *= 10
    d %= 2019

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

Solution (Python):
from collections import Counter

S = input()
n = len(S)

dp = [0]*(n+1)

dp[n-1] = int(S[-1])

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

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

Solution (Python):
import sys

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

INF = float('inf')


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)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    s = input()
    rem_l = [0]*2019
    rem_l[0] = 1
    curr_rem = 0
    for i, s_i in enumerate(s[::-1]):
        num = int(s_i)
        curr_rem = (curr_rem + num*pow(10,i,2019))%2019
        rem_l[curr_rem] += 1

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

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter
S = list(input())
S.reverse()
MOD = 2019

t = [0]
r = 1
for i in range(len(S)):
    q = (t[-1] + (int(S[i]) * r)) % MOD
    t.append(q)
    r *= 10
    r %= MOD

cnt = Counter(t)
cnt_mc = cnt.most_common()

ans = 0
for _, j in cnt_mc:
    if j >= 2:
        ans += j * (j - 1) // 2
        
print(ans)

Solution (Python):
from collections import Counter
S = list(input())
S.reverse()
MOD = 2019

t = [0]
r = 1
for i in range(len(S)):
    q = (t[-1] + (int(S[i]) * r) % MOD) % MOD
    t.append(q)
    r *= 10
    r %= MOD

cnt = Counter(t)
cnt_mc = cnt.most_common()

ans = 0
for _, j in cnt_mc:
    if j >= 2:
        ans += j * (j - 1) // 2
        
print(ans)

Solution (Python):
from collections import Counter

MOD = 2019
S = input()
S = tuple(map(int, reversed(S)))
counter = Counter([0])
digit = 1
cumsum = 0

for i in range(len(S)):
    cumsum += S[i] * digit % MOD
    cumsum %= MOD
    counter[cumsum] += 1
    digit = digit * 10 % MOD

print(sum([v * (v - 1) // 2 for v in counter.values()]))

Solution (Python):
from collections import Counter

MOD = 2019
S = input()
S = tuple(map(int, reversed(S)))
counter = Counter()
digit = 1
cumsum = 0
ans = 0

for i in range(len(S)):
    counter[cumsum] += 1
    cumsum += (S[i] * digit) % MOD
    cumsum %= MOD
    ans += counter[cumsum]
    digit *= 10
    digit %= MOD

print(ans)

Solution (Python):
import sys
def main():
    s=sys.stdin.readline().strip()
    d,m,p,c={0:1},0,1,0
    for a in reversed(s):
        m+=(int(a)*p)
        k=m%2019
        p=(p*10)%2019
        d[k]=d[k]+1 if k in d else 1
    for v in d.values():c+=v*(v-1)//2
    print(c)
if __name__=='__main__':main()

Solution (Python):
import sys
def main():
    s=sys.stdin.readline().strip()
    x=[0 for _ in [0]*2020]
    x[0],c=1,0
    m,d=0,1
    for i in reversed(s):
        m+=(int(i)*d)
        x[m%2019]+=1
        d=(d*10)%2019
    for v in x:c+=v*(v-1)//2
    print(c)
if __name__=='__main__':main()

Solution (Python):
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
mod = 2019
if __name__ == "__main__":
    s = input()
    n = len(s)
    dp = [0]*(mod)
    dp[0] = 1
    r = 0
    t = 1
    for i in reversed(s):
        r += int(i)*t
        r%=mod
        t*=10
        t%=mod
        dp[r] +=1
    ans = 0
    for i in dp:
        ans += i*(i-1)//2
    print(ans)

Solution (Python):
from sys import stdin, stdout

s = input()
n = len(s)
P = 2019



suffix_rems = [-1]*n
suffix_rems[-1] = int(s[-1])%P


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


special_keys = set()

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

    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):
import sys


import math
import collections

import bisect
import itertools
import fractions

import copy
import heapq
import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





def main():
    s = input()

    cnt = [0 for _ in range(2019)]
    cnt[0] += 1
    dec = 1
    num = 0
    for i in reversed(s):
        num += int(i) * dec
        num %= 2019
        dec *= 10
        dec %= 2019
        cnt[num] += 1

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from functools import reduce

def binom(n, r):
    if n < r or n < 0 or r < 0: return 0
    
    if n - r < r: r = n - r
    if r == 0: return 1
    elif r == 1: return n

    numerator = [n - r + 1 + k for k in range(r)]  
    denominator = [1 + k for k in range(r)]         

    
    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] //= pivot
                denominator[k] //= pivot
    
    
    return reduce(lambda x, y: x*y, numerator)

S = input()
cnt = [0] * 2019; cnt[0] += 1
t = 0
for i, s in enumerate(S[::-1]):
    t += int(s) * pow(10, i, 2019); t %= 2019
    cnt[t] += 1
ans = 0
for i in range(2019):
    if cnt[i] >= 2: ans += binom(cnt[i], 2)
print(ans)

Solution (Python):
import sys
from math import sqrt, gcd, ceil, log
from bisect import bisect
from collections import defaultdict
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))





def solve():
	s = inp().strip();
	dic = defaultdict(int); dic[0] = 1
	
	ans = 0; cum = 0
	for i in range(len(s)-1, -1, -1):
		cum += (int(s[i])*pow(10, (len(s)-i-1), 2019)) % 2019
		cum %= 2019
		dic[cum] += 1
	
	for i in dic:
		ans += ((dic[i])*(dic[i]-1))//2
	print(ans)






if __name__ == "__main__":
	solve()

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):
from collections import Counter
s = input()
MOD = 2019
ts = [0]
cur = 0
for i, j in enumerate(s[::-1], 1):
    cur = (cur + pow(10, i, MOD) * int(j)) % MOD
    ts.append(cur)
ct = Counter(ts)
res = 0
for k, v in ct.items():
    if v > 1:
        res += v * (v-1) // 2
print(res)

Solution (Python):
S = input()
r = 1
arr = [0]

for c in S[::-1]:
  arr.append((arr[-1] + int(c) * r) % 2019)
  r *= 10
  r %= 2019
from collections import Counter
ctr = Counter(arr)
ans = 0
for v in ctr.values():
  ans += v*(v-1)//2
print(ans)

Solution (Python):
from sys import stdin

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

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

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

Solution (Python):
def main():
    s = input()
    mod = 2019

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

    print(sum([r * (r - 1) // 2 for r in R]))


if __name__ == '__main__':
    main()

Solution (Python):
s = input()
res = 0
m = 1
p =[0]*2019
for i in map(int,s[::-1]):
    res +=i*m
    res %=2019
    p[res] +=1
    m *=10
    m %=2019
print(p[0]+sum([i*(i-1)//2 for i in p]))

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


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


def getList():
    return list(map(int, input().split()))


from collections import defaultdict, deque, Counter
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys


INF = 10 ** 17
MOD = 1000000007

from fractions import *


def inverse(f):
    
    return 1 / f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

MOD = 10 ** 9 + 7
def solve():
    MOD = 2019
    s = input().strip()
    acc = [0]
    revgen = pow(10, MOD-2, MOD)
    for c in s:
        num = int(c)
        acc.append((acc[-1] * 10 + num) % MOD)

    acc.reverse()
    mul = 1
    res = []
    for ac in acc:
        ac *= mul
        ac %= MOD
        res.append(ac)
        mul *= 10
        mul %= MOD
    res.reverse()

    
    cnt = Counter(res)
    ans = 0
    for v in cnt.values():
        ans += v * (v - 1)
    print(ans // 2)
    
    
    
def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    solve()

Solution (Python):
S=input()
n=len(S)
a=[0]*2019
MOD=2019
current=0
a[0]=1
for i in range(n):
  current=(current+int(S[n-1-i])*pow(10,i,MOD))%MOD
  a[current]+=1
ans=0
for i in range(2019):
  ans+=(a[i]*(a[i]-1))//2
print(ans)

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

dp = [[0]*2019 for _ in [0]*2]
ans = 0
for i,s in enumerate(S,1):
    s = int(s)
    i %= 2
    dpi = [0]*2019
    dpi1 = dp[1-i]
    dpi[s] += 1
    for j in range(2019):
        dpi[(j*10+s)%2019] += dpi1[j]
    dp[i] = dpi
    ans += dpi[0]

print(ans)

Solution (Python):
a = input()[::-1]
add = 0
ans = [1] + [0] * 2018
ans_int = 0
d = 1

for i in range(len(a)):
    add = (add + int(a[i]) * d) % 2019
    d = (10 * d) %2019
    ans[add] += 1

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

print(int(ans_int))

Solution (Python):
s = input()
n = len(s)
m = 2019
a = [0] * (n + 1)
b = [0] * (n + 1)
b[0] = 1
for i in range(1, n + 1):
    b[i] = b[i - 1] * 10 % m
c = [0] * m
c[0] += 1
ans = 0
for i in range(n - 1, -1, -1):
    w = (a[i + 1] + (ord(s[i]) - ord('0')) * b[n - 1 - i]) % m
    ans += c[w]
    c[w] += 1
    a[i] = w
print(ans)

Solution (Python):
S = input()
ans = {0:1}
memo = [0]
last = 1
for ind, s in enumerate(S[::-1]):
    memo.append((int(s) * last + memo[-1]) % 2019)
    last *= 10
    last %= 2019
    if(memo[-1] in ans):
        ans[memo[-1]] += 1
    else:
        ans[memo[-1]] = 1

res = 0
for key in ans.keys():
    res += ans[key]*(ans[key]-1)//2
print(res)