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






"""Module docstring
"""

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


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


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


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


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


LOG = None

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


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


if __name__ == "__main__":
    import doctest

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


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

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

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

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

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

Solution (Python):
import math
from functools import reduce
from collections import deque,defaultdict
import sys
sys.setrecursionlimit(10**7)

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

s = input()
X = list(map(int, list(s)))
n = len(s)

ruiseki = [0] * (n+1)
for i in (range(n-1, -1, -1)):
    ruiseki[i] = (X[i] * pow(10, (n-i-1), 2019) + ruiseki[i+1]) % 2019



ans = 0
count = defaultdict(int)

for x in ruiseki:
    
    ans += count[x]
    count[x] += 1

print(ans)

Solution (Python):
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

S = input()
N = len(S)

h = 2019
dp = [0]*h

ans = 0
for i in range(1, N+1):
    nextDp = [0]*h
    now = int(S[i-1])

    nextDp[now] += 1
    for k in range(h):
        n = (k * 10 + now) % h
        nextDp[n] += dp[k]

    ans += nextDp[0]
    dp = nextDp

print(ans)

Solution (Python):

"""
Created on Sun Apr 26 20:57:47 2020
"""

import sys


sys.setrecursionlimit(10 ** 9)


mod = 2019

S = input()
l = len(S)


a, b = [],[0]
s = 0
xx = [0 for _ in range(2019)]
xx[0] += 1
for i in range(l):
    s += int(S[-i-1])*pow(10,i,mod)
    s %= mod

    xx[s] += 1

ans = 0


def a(n):
    return n*(n+1)//2 

for i in range(len(xx)):
    if xx[i] > 1:
        ans += a(xx[i] - 1)

print(ans)

Solution (Python):

"""
Created on Sun Apr 26 20:57:47 2020
"""

import sys


sys.setrecursionlimit(10 ** 9)


mod = 2019

S = input()
l = len(S)


a, b = [],[0]
s = 0
xx = [0 for _ in range(2019)]
xx[0] += 1
for i in range(l):
    s += int(S[-i-1])*pow(10,i,mod)
    s %= mod

    xx[s] += 1

ans = 0


def a(n):
    return n*(n+1)//2 

for i in range(len(xx)):
    if xx[i] > 1:
        ans += a(xx[i] - 1)

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

S = list(input())
n = len(S)

dp = [0] * 2019
dp[0] = 1
tmp = 0
ten = 1
for i in range(n):
    tmp += int(S[n-1-i]) * ten
    tmp %= 2019
    ten *= 10
    ten %= 2019
    dp[tmp%2019] += 1


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

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

s=input()
len_s=len(s)
lst=[0]
dic=defaultdict(int)
dic[0]=1
ten=1
for i in range(len_s):
    lst.append((lst[i]+int(s[-i-1])*pow(10,i,2019))%2019)
    
    dic[lst[-1]]+=1


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

Solution (Python):
S = input()
 
mods = [0 for _ in range(2019)]
mods[0] = 1
t = 0
mod10 = 1
for s in reversed(S):
    t += int(s) * mod10
    t = t % 2019
    mod10 *= 10
    mod10 %= 2019
    mods[t] += 1

cnt = sum([m*(m-1)/2 for m in mods])
print(int(cnt))

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

Solution (Python):
import sys


def main():
    S = input()
    P = 2019

    ans,base = 0,1
    MOD_list = 0
    d = {}
    d[0] = 1

    for st in S[::-1]:
        num = int(st)
        MOD_list = (MOD_list+num*base)%P
        if MOD_list not in d:
            d[MOD_list] = 1
        else:
            d[MOD_list] += 1
        base *= 10
        base %= P

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

if __name__ == "__main__":
    main()

Solution (Python):
s = input()
length = len(s)
count_dict = {}

'''for i in range(length-4):
    for j in range(i+4,length+1):
        num = int(s[i:j])
        if num%2019 == 0:
            count += 1'''

num = int(s)%2019
count_dict[num] = 1




for i in range(1,length):
    num = (num-int(s[-i])*pow(10,(i-1),2019))%2019
    
    if num not in count_dict:
        count_dict[num] = 1
    else:
        count_dict[num] += 1


count = 0
for k,v in count_dict.items():
    count += v*(v-1)/2
    if k == 0:
        count += v

print(int(count))

Solution (Python):
import numpy as np




def solution():
    S = input()
    N = len(S)
    num = [0] * 2019
    num[0] = 1
    c, ans, dgt = 0, 0, 1
    for i in reversed(range(N)):
        c = (c + int(S[i]) * dgt) % 2019
        dgt *= 10
        dgt %= 2019
        ans += num[c]
        num[c] += 1
        
    print(ans)

solution()



def sample():
    x = -1
    count = 0
    for i in op:
        x += 1
        group = ""
        for j, name in enumerate(op, x):
            group += name
            if int(group) % 2019 == 0:
                count += 1
    print(count)

def checkValue():
    count = 0
    for i in range(length):
        group = ""
        for j in range(i, length):
            group += op[j]
            if int(group) % 2019 == 0:
                count += 1
    print(count)

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

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


S = input()
N = len(S)
P = 2019

if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    sys.exit()

num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1

print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import Counter

s = readline().rstrip().decode()[::-1]
m = 0
d = 1
memo = [0]
for check in s:
    m += int(check) * d
    m %= 2019
    d *= 10
    d %= 2019
    memo.append(m)
counter = Counter(memo)
ans = 0
for i in range(2020):
    ans += counter[i] * (counter[i] - 1) // 2
print(ans)

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

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

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

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

print(ans)

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    S = list(input())
    N = len(S)
    check = [0] * 2019
    ten = 1
    mod = 1
    check[mod] += 1
    for i in range(N):
        mod = (mod + int(S[N - i - 1]) * ten) % 2019
        ten = (ten * 10) % 2019
        check[mod] += 1
    answer = 0
    for i in range(2019):
        answer += ((check[i] - 1) * check[i]) // 2
    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
import collections
S = list(map(int, list(input())))
N = len(S)

dp = [0]*N
if N < 4:
    print(0)
    exit(0)

ans = 0

D = [0]*N
D[0] = 1
for i in range(1, N):
    D[i] = D[i-1]*10 % 2019
t = collections.defaultdict(int)
tmp = 0

t[0] += 1
for i in range(N):
    tmp += S[N-1-i]*D[i]
    tmp %= 2019
    t[tmp] += 1

for x in t:
    ans += t[x]*(t[x]-1) // 2




print(ans)

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

Solution (Python):
import numpy as np




def solution():
    S = input()
    N = len(S)
    num = [0] * 2019
    num[0] = 1
    c, ans, dgt = 0, 0, 1
    for i in range(N-1, -1, -1):
        c = (c + int(S[i]) * dgt) % 2019
        dgt *= 10
        dgt %= 2019
        ans += num[c]
        num[c] += 1
        
    print(ans)

solution()



def sample():
    x = -1
    count = 0
    for i in op:
        x += 1
        group = ""
        for j, name in enumerate(op, x):
            group += name
            if int(group) % 2019 == 0:
                count += 1
    print(count)

def checkValue():
    count = 0
    for i in range(length):
        group = ""
        for j in range(i, length):
            group += op[j]
            if int(group) % 2019 == 0:
                count += 1
    print(count)

Solution (Python):
def main():

    S = input()
    d = dict()
    d[0] = 1
    v = 0
    p = 1
    for i in range(len(S)):
        v = v + int(S[len(S)-i-1]) * p
        v %= 2019
        d[v] = d.get(v, 0) + 1
        p *= 10
        p %= 2019

    ans = 0
    for v in d:
        ans += d[v] * (d[v] - 1) // 2
    return ans


if __name__ == '__main__':
    print(main())

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    S = list(input())
    N = len(S)
    
    d = defaultdict(int)
    d[0] = 1
    ans = 0
    tmp = 0
    for i in range(N):
        si = int(S[N - 1 - i])
        tmp = (tmp + si * pow(10, i, 2019)) % 2019
        ans += d[tmp]
        d[tmp] += 1
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import math
import collections


S = input()


N = len(S)
P = 2019
ans = 0
juu = 1
S = S[::-1]
amari = 0
amaris = [0] * (P) 
if P == 2 or P == 5:
    for i,c in enumerate(S):
        n = int(c)
        if n % P == 0:
            ans += N - i
else:


    for c in S:
        i = int(c)
        amari += (i * juu)
        amari %= P
        amaris[amari] += 1
        juu *= 10
        juu %= P


    amaris[0] += 1
    for temp in amaris:
        ans += temp * (temp - 1) //2
print(ans)

Solution (Python):
from collections import Counter

S = input()

ans = 0
mod_list = [0] * len(S)
mod_list[-1] = int(S[-1])
m = 1
for i in range(2, len(S) + 1):
    m = (10 * m) % 2019
    mod_list[-i] = (mod_list[-i + 1] + (int(S[-i]) * m)) % 2019

mod_counter = Counter(mod_list)
mod_counter[0] += 1

ans = 0
for _, v in mod_counter.items():
    ans += v * (v - 1) // 2

print(ans)

Solution (Python):
S = input()
n = len(S)
res = 0
cur = 0
count = [0] * 2020
for i, c in enumerate(map(int, S)):
    cur = (cur * 10 + c) % 2019
    if cur == 0:
        res += 1
    temp = (cur * pow(10, (n - i), 2019)) % 2019
    res += count[temp]
    count[temp] += 1
print(res)

Solution (Python):
import sys

from collections import Counter

def main():
    S = input()
    P = 2019

    ans,base = 0,1
    MOD_list = [0]

    for st in S[::-1]:
        num = int(st)
        MOD = (MOD_list[-1]+num*base)%P
        MOD_list.append(MOD)
        base *= 10
        base %= P

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

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    from collections import Counter
    P = 2019
    S = [int(s) for s in input()]
    N = len(S)
    ans = 0
    if P == 5 or P == 2:
        for i, s in enumerate(S, start=1):
            if s % P == 0:
                ans += i
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1], start=1):
            
            acc[i] = (s * d + acc[i-1]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
S=list(map(int,input()))
P=2019
N=len(S)
if P not in [2,5]:
  pt = [1]
  for i in range(N):
    pt.append(pt[-1]*10%P)
  dp = [(S[0]*pt[N-1])%P]
  for i in range(1,N):
    dp.append((dp[-1]+S[i]*pt[N-1-i])%P)

  c = Counter(dp)
  ans = sum(u*(u-1)//2 for u in c.values())
  print(ans+c[0])
elif P==2:
  S = [int(c) for c in input()]
  ans = 0
  for i in range(N):
    if S[i]%2==0:
      ans += i+1
  print(ans)
else:
  ans = 0
  S = [int(c) for c in input()]
  for i in range(N):
    if S[i]%5==0:
      ans += i+1
  print(ans)

Solution (Python):
import sys

from collections import Counter

def main():
    S = input()
    P = 2019

    ans,base = 0,1
    MOD_list = [0]

    for st in S[::-1]:
        num = int(st)
        MOD = (MOD_list[-1]+num*base)%P
        MOD_list.append(MOD)
        base *= 10
        base %= P

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

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read
s = input()
res = [0]*2019
res[0] = 1
t = 1
now = 0
for i in s[::-1]:
    i = int(i)
    now += i*t
    now %= 2019
    res[now] += 1
    t = t*10%2019
 
ans = 0    
for i in res:
    ans += i*(i-1)//2
 
print(ans)

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


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



ss = input()























ls=len(ss)


    




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



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






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

Solution (Python):
S = list(input())
n = len(S)
res = 0
cur = 0
count = [0] * 2020
count[0] = 1
for i, c in enumerate(map(int, S)):
    cur = (cur * 10 + c) % 2019
    temp = (cur * pow(10, (n - i), 2019)) % 2019
    count[temp] += 1
print(sum(c * (c - 1) // 2 for c in count))

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

ans = 0
cnt = [0] * 2019
a = 1
s = 0

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

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

Solution (Python):


S = input()
P = 2019
N = len(S)
num = [0] * P
num[0] = 1
c = 0
ans = 0
dgt = 1
for i in range(N-1, -1, -1):
    c = (c + int(S[i]) * dgt) % P
    dgt *= 10
    dgt %= P
    ans += num[c]
    num[c] += 1
 
print(ans)

Solution (Python):
def main():
    S = list( map( int, list( input())))
    N = len(S)
    A = [0]*2019
    Q = 2019
    now = 0
    A[0] = 1
    for i in range(N-1,-1,-1):
        now = (S[i]*pow(10,N-1-i,Q)+now)%Q
        A[now] += 1

    ans = 0
    for a in A:
        ans += a*(a-1)//2
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
def resolve():
    s = input()
    lens = len(s)

    mod1 = []
    for i in reversed(range(lens)):

        mod1.append((int(s[i]) * pow(10, lens-i-1, 2019))%2019)
    mod2 = {}
    sums = 0
    for i in range(lens):
        sums += int(mod1[i])
        sums %= 2019
        if sums in mod2:
            mod2[sums] += 1
        else:
            mod2[sums] = 1
    if 0 in mod2:
        mod2[0] +=1

    keys = list(mod2.keys())
    ans = 0
    for i in range(len(mod2)):
        if mod2[keys[i]] >1:
            test = mod2[keys[i]]
            ans += test*(test-1)//2
    print(ans)
resolve()

Solution (Python):

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

ans = 0
for i in rui:
    if i >= 2:
        ans += (i * (i - 1) // 2)

print(ans)

Solution (Python):
from collections import Counter


mod = 2019
S = map(int, reversed(input()))

mods = [0]
num = 0
digit = 1
for s in S:
    num += s * digit
    num %= mod
    mods.append(num)
    digit = digit * 10 % mod

counter = Counter(mods)
ans = 0
for count in counter.values():
    ans += count * (count-1) // 2
print(ans)

Solution (Python):
from collections import Counter

s = input()
mod1 = 673
mod2 = 3

num1 = 0
num2 = 0
li1 = []
li2 = []
pw1 = 10
pw2 = 10
for i, e in enumerate(s, 1):
    num1 *= 10
    num1 += int(e)
    num1 %= mod1
    inv = pow(pw1, mod1 - 2, mod1)
    li1.append(num1 * inv % mod1)

    num2 *= 10
    num2 += int(e)
    num2 %= mod2
    inv = pow(pw2, mod2 - 2, mod2)
    li2.append(num2 * inv % mod2)

    pw1 *= 10
    pw1 %= mod1
    pw2 *= 10
    pw2 %= mod2

li = [0] + [10 * e1 + e2 for e1, e2 in zip(li1, li2)]
c = Counter(li)

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

print(ans)

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

def main():
    S = list(input())
    S.pop()
    m = 2019
    div_list = [0]*m
    num = 0
    for i, l in enumerate(reversed(S)):
        num += pow(10, i, m)*int(l)
        div_list[num%m] += 1

    div_list[0] += 1
    ans = 0
    for item in div_list:
        ans += int(item*(item-1)/2)

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
S = list(input())
n = len(S)
cur = 0
count = [0] * 2020
count[0] = 1
for i, c in enumerate(map(int, S[::-1])):
    cur = (cur + c * pow(10, i, 2019)) % 2019
    count[cur] += 1
    
print(sum(c * (c - 1) // 2 for c in count))

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

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

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

print(count)

Solution (Python):


def solve():

    s = input()
    mod = 2019
    remains = [0]*mod

    ans = 0
    now = 0
    remains[0] = 1
    for i, val in enumerate(s[::-1]):
        now += int(val) * pow(10, i, mod)
        now %= mod
        ans += remains[now]
        remains[now] += 1

    print(ans)


if __name__ == "__main__":
    solve()

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

mod_table=[0]*P
mod_table[0]=1

modp=0
mod10=1
for i in reversed(range(len(S))):
  si=int(S[i])
  modp=(si*mod10+modp)%P
  mod_table[modp]+=1
  mod10=(mod10*10)%P
  
answer=0
for m in mod_table:
  answer+=m*(m-1)//2
  
print(answer)

Solution (Python):
import numpy as np
s = list(map(int,input()))
n = len(s)
ans = 0
mod = 2019
past = s[n-1]
ima = 0
d = dict()
d[s[n-1]] = 1
now = 10
for i in range(1,n):
    ima = (past+s[n-i-1]*now)%mod
    if ima == 0:
        ans += 1
    if ima in d:
        d[ima] += 1
    else:
        d[ima] = 1
    past = ima
    now = (now*10)%mod

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

print(ans)

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

rem = [0]*P
mod = 0
ten = 1
rem[mod]=1
for i in range(N):
    mod=(mod+int(S[N-i-1])*ten)%P
    ten=ten*10%P
    rem[mod]+=1
for j in rem:
    ans+=(j*(j-1))//2
print(ans)

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):
import sys
sys.setrecursionlimit(10**9)


S = input()
N, P = len(S),2019

if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    sys.exit()

num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1

print(ans)

Solution (Python):
S = str(input())
s = len(S)
cnt = 0
A = [0]*2019
r = 0
for i in range(s):
  x = (r+pow(10, i, 2019)*int(S[s-i-1]))%2019
  A[x] += 1
  r = x
  
for i in range(1,2019):
  if A[i] >= 2:
    cnt += A[i]*(A[i]-1)//2
cnt += A[0]*(A[0]+1)//2

print(cnt)

Solution (Python):
P=2019
S = input()
N=len(S)
count=[0]*P
ans = 0
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):
from collections import defaultdict


s = input()[::-1]
cntr = defaultdict(int)
cntr[0] += 1
tens = 1
n = 0
for c in s:
    n += tens * int(c) % 2019
    n %= 2019
    cntr[n] += 1
    tens = tens * 10 % 2019

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

Solution (Python):
import sys
from collections import Counter
readline = sys.stdin.buffer.readline

s = readline().rstrip().decode('utf-8')
n = len(s)
m = 2019
lst1 = [0]*len(s)
res = ""
for i in range(n):
    res = int(str(res)+s[i])
    res %= m
    lst1[i] = res
 
ans = 0
 
if m == 2 or m == 5:
    for i in range(n):
        if lst1[i] == 0:
            ans += i+1
 
 
else:
    s = s[::-1]
    dig = 1
    lst1 = [0]*n
    for i in range(n):
        if i == 0:
          lst1[i] = int(s[i])%m
          continue
          
        dig *= 10
        dig %= m
        lst1[i] = lst1[i-1] + dig*int(s[i])
        lst1[i] %= m
    c = Counter(lst1)
    
    for i in c.values():
        
        ans += i*(i-1)//2
    ans += c[0]
print(ans)

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    S=readline().strip()
    li=[0]*2019
    n=int(S[-1])%2019
    m=1
    for i in range(len(S)):
        if i==0:
            pass
        else:
            m*=10
            m%=2019
            l=int(S[len(S)-i-1])
            n+=m*l
            n%=2019
        li[n]+=1

    res=li[0]
    for i in range(2019):
        res+=li[i]*(li[i]-1)//2
    print(res)
    
if __name__=="__main__":
    main()

Solution (Python):
s = input()
ans = 0
U = [0 for i in range(2019)]
mod = 2019
sum_i_to_n = 0
for i in range(len(s)-1,-1,-1):
    sum_i_to_n += int(s[i])* pow(10,len(s)-i-1,mod)
    sum_i_to_n %= mod
    if sum_i_to_n % mod == 0:
        ans += 1
    ans += U[sum_i_to_n]
    U[sum_i_to_n] += 1
print(ans)

Solution (Python):
s = input()[::-1]
l = len(s)
x = [0 for _ in range(2019)]
x[0] += 1
k = 0
p = 1
for si in s:
    k += int(si) * p % 2019
    k %= 2019
    x[k] += 1
    p *= 10
    p %= 2019
 
ans = 0
for xi in x:
    ans += max(0, xi * (xi - 1) // 2)
print(ans)

Solution (Python):
s = input()[::-1]
l = len(s)
x = [0 for _ in range(2019)]
x[0] += 1
k = 0
p = 1
for si in s:
    k += int(si) * p % 2019
    k %= 2019
    x[k] += 1
    p *= 10
    p %= 2019

ans = 0
for xi in x:
    ans += max(0, xi * (xi - 1) // 2)
print(ans)

Solution (Python):

S=input()
s=[0 for i in range(len(S))]

for i in range(len(S)):
    s[i]=int(S[i])
CHECK=[0 for i in range(2021)]
ans=0
temp=0
for i in range(1,len(s)+1):
    
    temp=(temp+s[-i]*pow(10,i-1,2019)+2019*2)%2019
    
    
    CHECK[temp]+=1
for i in CHECK:
    ans+=i*(i-1)//2

ans+=CHECK[0]
 
print(ans)

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

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

s = list(input())
n = len(s)-1

res = 0

d = dict()
mod = 2019
d[0] = 1

tmp = 0
for i in range(n-1,-1,-1):
    tmp = (tmp + int(s[i])*pow(10,n-1-i,mod))%mod
    if tmp in d:
        res += d[tmp]
        d[tmp] += 1
    else:
        d[tmp] = 1

print(res)

Solution (Python):
from collections import Counter

S = input()

p = 2019
N = len(S)


m = [(int(S[i]) * pow(10, N-i, p)) % p for i in range(N)]


r = [0] * N
r[0] = m[0]
for ri in range(1, N):
    r[ri] = (r[ri-1] + m[ri]) % p


c = Counter(r)

ans = 0
for ci in [cv for cv in c.values() if cv >= 2]:
    ans += ci * (ci-1) // 2

if 0 in c.keys():
    ans += c[0]

print(ans)

Solution (Python):
S=list(input())
S.reverse()
N=len(S)
R=[0]*N
R10=[0]*N
m=2019
K=0

R10[0]=1
R[0]=int(S[0])%m
for i in range(1,N):
    R10[i]=(R10[i-1]*10)%m
    R[i]=(R[i-1]+int(S[i])*R10[i])%m
d={}
for i in range(2019):
    d[i]=0

for i in range(N):
    d[R[i]]+=1
ans=0
for i in range(2019):
    if i == 0:
        ans += d[i]
        ans +=d[i]*(d[i]-1)//2
    else:
        ans +=d[i]*(d[i]-1)//2
print(ans)

Solution (Python):
S=list(map(int,input()[::-1]))
lenS=len(S)
cnt = [0]*2019
tmp = 0
for n,i in enumerate(S):
    tmp += i*pow(10,n,2019)
    cnt[tmp%2019]+=1
ans = cnt[0]*(cnt[0]+1)//2
for i in cnt[1:]:
    ans += i*(i-1)//2
print(ans)

Solution (Python):
import collections
MOD = 2019

def mod(n):         
  return n % MOD

def modpow(a, n):   
    res = 1  
    digit = len(str(bin(n))) - 2
    for i in range(digit):
      if (n >> i) & 1:
        res *= mod(a)
        res = mod(res)
      a = mod(a**2)
    return mod(res)

s = input()
lst = []
n = 0
for i in range(len(s)):
  n += mod(int(s[len(s)-i-1])*modpow(10, i))
  lst.append(mod(n))
lst.append(0)
lst.sort()
ans = 0
counter = 1
stock = lst[0]
for i in range(1, len(lst)):
  if stock == lst[i]:
    counter += 1
  else:
    ans += counter*(counter - 1)//2
    counter = 1
    stock = lst[i]
if counter >= 2:
  ans += counter*(counter - 1)//2
print(ans)

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

from collections import defaultdict

s = ns()
d = defaultdict(int)
d[0] += 1
k = 1
n = 0
for i in range(len(s))[::-1]:
    n += int(s[i])*k%2019
    n%=2019
    d[n] += 1
    k = (k*10)%2019

ans = 0

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

print(ans)

Solution (Python):
from collections import defaultdict
def power_func(a, n, p=2019):
    bi = str(format(n, "b"))  
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
            res=(res*a) %p
    return res

s=input()
d=[]
for i in range(len(s)):
    d.append(int(s[i])*power_func(10,len(s)-i-1,2019)%2019)
d1=[d[0]]
for g in range(1,len(s)):
    d1.append((d1[-1]+d[g])%2019)

di = defaultdict(int)
ans=0
for i in range(len(s)):
    di[d1[i]]+=1
    if d1[i]==0:
        ans+=1
    ans+=di[d1[i]]-1
print(ans)

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

S = input()
N = len(S)
P = 2019
if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    sys.exit()

num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1

print(ans)

Solution (Python):
P = 2019
S = input()
N = len(S)
 
if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    exit()
 
num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1
 
print(ans)

Solution (Python):
from collections import defaultdict
from math import factorial

s = input()

rs = list()
r = 0
dr = 1
for i in range(len(s)):
    rt = (dr * int(s[-(i + 1)])) % 2019
    r = (r + rt) % 2019
    dr = (dr * 10) % 2019
    rs.append(r)

d = defaultdict(lambda: 0)

d[0] = 1
for r in rs:
    d[r] += 1

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

a = 0
for ss in s + 'x':
    if ss == '0':
        a += 1
        res -= 1
    else:
        if a >= 2:
            res -= a * (a - 1) / 2
        a = 0

print(int(res))

Solution (Python):
import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    val = [0] * (2019)
    tenfactor = 1
    cur = 0
    val[cur] += 1
    for i in range(N):
        cur = (cur + int(S[N - i - 1]) * tenfactor) % 2019
        tenfactor = (tenfactor * 10) % 2019
        val[cur] += 1

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


if __name__ == "__main__":
    main()

Solution (Python):
S = str(input())
l = [0]* len(S)
q = 1
l[0] = int(S[len(S) - 1])
for i in range(1,len(S)):
    t = int(S[len(S) - i - 1])
    q = q * 10 % 2019
    l[i] = (t*q + l[i - 1]%2019)%2019
l.sort()
m = [0] * len(S)
k = 1
for i in range (len(S) - 1):
    if l[i] != l[i + 1]:
        m[i] = int(k*(k-1)/2)
        k = 1
    else:
        m[i] = 0
        k += 1
if k != 1:
    m[len(S) - 1] = int(k*(k-1)/2)
a = 0
for i in range(len(S)):
    if l[i] == 0:
        a += 1
    else:
        break
print(sum(m) + a)