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()
N = len(S)
P = 2019


cnt = 0

table = [0] * P 
Ui = 0
ten = 1

S = S[::-1]
table[0] = 1 

for i in range(N):
    Ui = (Ui + int(S[i]) * ten) % P 
    
    cnt += table[Ui] 
    
    table[Ui] += 1 
    ten = (ten * 10) % P 
print(cnt)

Solution (Python):
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

MOD = 2019

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return a*b%MOD


def extgcd(a,b):
    r = (1,0,a)
    w = (0,1,b)
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return (w[0],w[1])

def mod_inv(a):
    x,_  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res    
s=s_in()

from collections import Counter


p = 2019
c = Counter()
current = int(s[len(s)-1])
c[0]+=1
c[current]+=1

for i in range(len(s)-2, -1,-1):
    current = mod_add(current, mod_mul(int(s[i]), mod_pow(10, len(s)-i-1)))

    c[current%p] += 1


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

print(res)

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

    l = [[[] for j in range(3)] for i in range(673)]
    l[0][0].append(0)
    mo = 0
    ten = 1
    mod = 673
    now = 0
    ans = 0
    for i in range(len(s)):
        a = int(s[i])*ten
        mo = (mo+a)%3
        now = (now+a)%mod
        if l[now][mo]:
            ans += len(l[now][mo])
        l[now][mo].append(i+1)
        ten *= 10
        ten %= 2019
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):
n = input()
l = len(n)
key = [0]*2019
mod = 1
judge = 0
for i in range(l):
  judge += ((mod%2019)*int(n[l-i-1]))%2019
  judge %= 2019
  k = judge%2019
  key[k] += 1
  mod *= 10
  mod %= 2019

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

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

Solution (Python):
s=input()
l=len(s)
se=dict()
k=0
for i in range(l-1,-1,-1):
    
    k+=(pow(10,l-1-i,2019)*int(s[i]))
    k%=2019
    if k in se:
        se[k]+=1
    else:
        se[k]=1

ans=0
for j in se:
    i=se[j]
    if i>1:
        ans+=(i*(i-1)//2)
    if j==0:
        ans+=i
print(ans)

Solution (Python):
from collections import defaultdict

S = input()
S = S[::-1]
N = len(S)
MOD = 2019
D = defaultdict(int)
res = 0
p = 1
for i in range(N):
    tmp = res + int(S[i]) * p
    tmp %= MOD
    D[tmp] += 1

    res = tmp
    p *= 10
    p %= 2019 

ans = 0
for k,v in zip(D.keys(), D.values()):
    if k == 0:
        ans += v
        ans += v * (v - 1) //2
    elif v >= 2:
        ans += v * (v - 1) // 2

print(ans)

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

mod = {}

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

ans = 0
for x in mod.keys():
  if x == 0:
    ans += mod[x] * (mod[x] + 1) // 2
  else:
    ans += mod[x] * (mod[x] - 1) // 2

print(ans)

Solution (Python):
s = input()
n = len(s)
MOD=2019
ls=[0]*n
ls[-1] = int(s[-1])
freq=[0]*2019
for i in reversed(range(1,n)):
    ls[i-1] = (ls[i]+int(s[i-1])*pow(10,n-i,MOD))%MOD
    
for i in range(n):
    freq[ls[i]]+=1
ans=0
for i in range(2019):
    if i==0:
        ans+=freq[i]*(freq[i]+1)//2
    else:
        ans+=freq[i]*(freq[i]-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):
from collections import defaultdict as dict

s = input()
n = len(s)
p = 2019
a = []
for x in s:
    a.append(int(x))

x = 0
mem = dict(int)
mem[0] = 1
ans = 0
a.reverse()
d = 1
for y in a:
    x += d * y
    x %= p
    d = (d * 10) % p
    ans += mem[x]
    mem[x] += 1

print(ans)

Solution (Python):
s = str(input())
MOD = 2019
modl = [0 for _ in range(2019)]
modl[0] = 1
cnt = 1
x = 0
for i in range(len(s)):
	x = (x+(int(s[len(s)-1-i])*cnt))%MOD
	modl[x] += 1
	cnt = (cnt*10)%MOD

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

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

N = len(S)
A = [0]
base = 1
for i in range(N):
	A.append((A[-1] + S[N-1-i] * base) % 2019)
	base = base * 10 % 2019
A.sort()
ans = 0
cnt = 1
for i in range(N):
	if i == N-1:
		if cnt > 1:
			cnt += 1
			ans += (cnt * (cnt - 1)) // 2
	elif A[i] == A[i+1]:
		cnt += 1
	else:
		ans += (cnt * (cnt - 1)) // 2
		cnt = 1
print(ans)

Solution (Python):
from collections import Counter

p = 2019
s = list(map(int, input()))

ans = 0

s = s[::-1]
power = 1
t = [0] * len(s)
t[0] = s[0] % p
for i in range(1, len(s)):
    power = power * 10 % p
    t[i] = (t[i-1] + s[i] * power) % p

counter = Counter(t)
for i in counter.values():
    ans += i * (i-1) // 2
ans += counter[0]
print(ans)

Solution (Python):
S=input()
N=len(S)
a=[0]*(N+1)
m=2019
for i,c in enumerate(reversed(S)):
    a[i+1]=(int(c)*pow(10,i,m)+a[i])%m
from collections import Counter
c=Counter(a)
r=0
for k,v in c.items():
    r+=v*(v-1)//2
print(r)

Solution (Python):
from collections import Counter

def main():
    s = list(map(int,input()[::-1]))

    t = []
    m = 0
    for i,s_i in enumerate(s):
        m = m+s_i*pow(10,i,2019)
        t.append(m%2019)
    
    c = Counter(t)
    ans = c[0]
    for i in c.values():

        ans += i*(i-1)//2
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
x = input()
ll = len(x)

now = 0
mod_dict = {}
mod_dict[0] = 1
for i in reversed(range(len(x))):
    now = now + int(x[i]) * pow(10, (ll - i - 1), 2019)

    now %= 2019
    if now not in mod_dict:
        mod_dict[now] = 1
    else:
        mod_dict[now] = mod_dict[now] + 1

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

Solution (Python):
from collections import Counter
Next = [i*10 % 2019 for i in range(2019)]
S = input()
L = list(reversed(S))
Amaris = []
amari = 0
kurai = 1
for l in L:
    amari += kurai*int(l)
    amari %= 2019 
    kurai *= 10
    kurai %= 2019
    Amaris.append(amari)
C = Counter(Amaris)
ans = 0 
for d in C.values():
    ans += d*(d-1)//2
print(ans + C[0])

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
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)
    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):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

s = ins()
n = len(s)
t = [-1]*(n+1)
r = [0]*2019
c = 1
t[n] = 0
r[0] = 1
t[n-1] = int(s[n-1])
r[t[n-1]] = 1
for i in range(n-2,-1,-1):
    c = (c*10)%2019
    t[i] = (t[i+1]+int(s[i])*c)%2019
    r[t[i]] += 1

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

Solution (Python):

MOD = 10 ** 9 + 7

def main():
    for _ in inputt(1):
        S = input()
        D = [0] * 2019
        t = 0
        for ch in S:
            c = ord(ch) - 48
            nD = [0] * 2019
            nD[c] = 1
            for i, d in enumerate(D):
                nD[(i * 10 + c) % 2019] += d
            D = nD
            t += D[0]
        print(t)







from math import *
from heapq import *
from itertools import *
from functools import reduce, lru_cache, partial
from collections import Counter, defaultdict
import re, copy, operator, cmath
import sys, io, os, builtins
sys.setrecursionlimit(1000)





BUFSIZE = 8192
class FastIO(io.IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = io.BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(io.IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
def print(*args, **kwargs):
    if args:
        sys.stdout.write(str(args[0]))
        split = kwargs.pop("split", " ")
        for arg in args[1:]:
            sys.stdout.write(split)
            sys.stdout.write(str(arg))
    sys.stdout.write(kwargs.pop("end", "\n"))
def debug(*args, **kwargs):
    print("debug", *args, **kwargs)
    sys.stdout.flush()
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip()
inputt = lambda t = 0: range(t) if t else range(int(input()))
inputs = lambda: input().split()
inputi = lambda: map(int, inputs())
inputl = lambda t = 0, k = lambda: list(inputi()): [k() for _ in range(t)] if t else list(k())





def len(a):
    if isinstance(a, range):
        return -((a.start - a.stop) // a.step)
    return builtins.len(a)
def bisect_left(a, x, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    while lo < hi:
        mid = (lo + hi) // 2
        if key(a[mid]) < x: lo = mid + 1
        else: hi = mid
    return lo
def bisect_right(a, x, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    while lo < hi:
        mid = (lo + hi) // 2
        if x < key(a[mid]): hi = mid
        else: lo = mid + 1
    return lo
def insort_left(a, x, key = None, lo = 0, hi = None):
    lo = bisect_left(a, x, key, lo, hi)
    a.insert(lo, x)
def insort_right(a, x, key = None, lo = 0, hi = None):
    lo = bisect_right(a, x, key, lo, hi)
    a.insert(lo, x)
do_nothing = lambda x: x
bisect = bisect_right
insort = insort_right
def index(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    i = bisect_left(a, x, key, lo, hi)
    if lo <= i < hi and key(a[i]) == x: return a[i]
    if default != None: return default
    raise ValueError
def find_lt(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_left(a, x, key, lo, hi)
    if lo < i <= hi: return a[i - 1]
    if default != None: return default
    raise ValueError
def find_le(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_right(a, x, key, lo, hi)
    if lo < i <= hi: return a[i - 1]
    if default != None: return default
    raise ValueError
def find_gt(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_right(a, x, key, lo, hi)
    if lo <= i < hi: return a[i]
    if default != None: return default
    raise ValueError
def find_ge(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_left(a, x, key, lo, hi)
    if lo <= i < hi: return a[i]
    if default != None: return default
    raise ValueError






class Tree:
    def __init__(n):
        self._n = n
        self._conn = [[] for _ in range(n)]
        self._list = [0] * n
    def connect(a, b):
        pass






class Sieve:
    def __init__(self):
        self._n = 6
        self._list = [2, 3, 5, 7, 11, 13]
    def extend(self, n):
        pass


sieve = Sieve()
def isprime(n):
    pass
def prime(n):
    pass
def factorint(n):
    factordict = defaultdict(int)
    for i in sieve:
        if n <= i * i:
            break
        while not n % i:
            factordict[i] += 1
            n //= i
    if n != 1:
        factordict[n] += 1
    return factordict





if __name__ == "__main__":
    main()

Solution (Python):
import sys,math,copy,queue,itertools,bisect,collections
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
INF = 10**18
MOD = 2019
DD = ((1,0),(0,1),(-1,0),(0,-1))

s = [int(x) for x in sys.stdin.readline().rstrip()]
amari = {0:1}
m = 0
t = 1
for i in range(len(s)-1,-1,-1):
    m = (t *s[i] + m) % MOD
    if m in amari:
        amari[m] += 1
    else:
        amari[m] = 1
    t = (t * 10) % MOD

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

print (ans)

Solution (Python):
def main():
    mod = 2019
    s = input()
    dp = []
    mods = {}
    for i in range(len(s)):
        x = int(s[i])*pow(10,len(s)-1-i,mod)
        x %= mod
        if not dp:
            dp.append(x)
        else:
            dp.append(dp[-1]+x)

        dp[-1] %= mod
        if dp[-1] not in mods.keys():
            mods[dp[-1]] = 0

        mods[dp[-1]] += 1

    ans = 0
    for i in mods.keys():
        if i == 0:
            ans += mods[i]

        x = mods[i]
        ans += x*(x-1)//2

    print(ans)


main()

Solution (Python):
s = input()

remain = [0]*2020
now = 0
ans = 0
for i in range(len(s)-1, -1, -1):
    now += int(s[i])*pow(10, len(s)-i-1, 2019)
    ans += remain[now%2019]
    remain[now%2019] += 1

ans += remain[0]

print(ans)

Solution (Python):
from collections import Counter
p = 2019
s = list(map(int, input()))
n = len(s)
ans = 0
if p == 2:
    for i, c in enumerate(s):
        if c % 2 == 0:
            ans += i + 1
elif p == 5:
    for i, c in enumerate(s):
        if c % 5 == 0:
            ans += i + 1
else:
    l = [0] * (n + 1)
    for i, c in enumerate(s):
        l[i + 1] = l[i] + pow(10, n - i - 1, p) * c
        l[i + 1] %= p
    for v in Counter(l).values():
        ans += v * (v - 1) // 2
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
s=input().rstrip()
n=len(s)
l=[0]
for i in range(n):
    x=int(s[n-1-i])
    y=l[-1]+x*pow(10,i,2019)
    l.append(y%2019)
c=[0]*2019
for i in l:
    c[i]+=1
ans=0
for i in c:
    ans+=i*(i-1)//2
print(ans)

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

S = input()
L = len(S)

dp = [0] * (L + 1)
pow = [1] * (L + 1)
cnt = [0] * 2019

ans = 0
for i in range(L):
    pow[i + 1] = pow[i] * 10 % 2019
    dp[i + 1] = (dp[i] + int(S[L - i - 1]) * pow[i]) % 2019
    if dp[i + 1] == 0:
        cnt[dp[i + 1]] += 1
        ans += cnt[dp[i + 1]]
    else:
        ans += cnt[dp[i + 1]]
        cnt[dp[i + 1]] += 1

print(ans)

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

S = readline().strip()
S = list(map(int, S))
N = len(S)
P = 2019

rems = [0] * N
a = 1
b = 0
for i in range(N):
    b = (b + (a * S[N - i - 1]) % P) % P
    rems[N - i - 1] = b
    a = a * 10 % P

rems = rems + [0]

counts = [0] * P


for i in range(len(rems)):
    counts[rems[i]] += 1

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

print(ans)

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

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

a = {}
for i in range(N + 1):
  if T[i] in a:
    a[T[i]] += 1
  else:
    a[T[i]] = 1

num = 0
if P % 2 == 0 or P % 5 == 0:
  for i in range(N):
    if int(S[i]) % P == 0:
      num += 1 + i
else:
  for k in a:
    num += a[k] * (a[k] - 1) // 2

print(num)

Solution (Python):
S = input()

ls = len(S)
cur_num = 0
cur_r = 0
r = [0]*ls
ans = 0
for i in range(ls):
    if i == 0:
        r[i] = (int(S[ls-i-1])*pow(10,i,2019))%2019
    else:
        r[i] = r[i-1] + (int(S[ls-i-1])*pow(10,i,2019))%2019
        r[i] %= 2019

from collections import Counter
c = Counter(r)


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

Solution (Python):
from collections import defaultdict

S = input()
N = len(S)
dp = [0 for _ in range(N+1)]

MOD = 2019

dp[-1] = int(S[-1])
tmp = 10
for i in range(N-1, 0, -1):
    m = int(S[i-1])
    dp[i] = (dp[i+1]+tmp*m)%MOD
    tmp = tmp*10%MOD

d = defaultdict(int)

for i in range(N+1):
    d[dp[i]] += 1

ans = 0
for k in d.keys():
    ans += d[k]*(d[k]-1)//2

print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
n = len(s)
t = []
for i in range(n):
    t.append(int(s[i])*pow(10,n-i-1,2019))
t = list(accumulate(t))
u = [i % 2019 for i in t]
u = list(Counter(u).items())
ans = 0
for i,j in u:
    if i == 0:
        ans += j
    if j >= 2:
        ans += j*(j-1) // 2
print(ans)

Solution (Python):
from collections import defaultdict
s = input()
n = len(s)
p = 2019
sur1 = [int(s[0]) % p]
sur2 = [int(s[-1]) % p]
sur10 = [1 % p]
for i in range(n - 1):
    sur1 += [(sur1[i] * 10 + int(s[i + 1])) % p]
    sur10 += [(sur10[i] * 10) % p]
    sur2 += [(sur2[i] + sur10[i + 1] * int(s[-i - 2])) % p]

ans = 0
d = defaultdict(int)
for x in sur2:
    d[x] += 1

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

Solution (Python):
s=input()
a=0
now=1
l=[0]*2019
for i in list(s)[::-1]:
    a=(a+now*int(i))%2019
    l[a]+=1

    now*=10
    now%=2019
ans=0
for i in l:
    ans+=(i-1)*i//2
print(ans+l[0])

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

digitssum = [0] * n

for i, c in enumerate(s):
    digitssum[i] = int(c) * pow(10, n-i-1, 2019)

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

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

for d in digitssum:
    counter[d] += 1

print(sum((counter[i] * (counter[i]-1) // 2) for i in range(2019)))

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

dp = [0] * MOD
dq = [0] * MOD
ans = 0

for i in range(len(s)):
    tmp = int(s[i])
    if i % 2 == 0:
        for val in range(MOD):
            dp[((val * 10) + tmp) % MOD] += dq[val]
            dq[val] = 0
        dp[tmp] += 1
        ans += dp[0]

    else:
        for val in range(MOD):
            dq[((val * 10) + tmp) % MOD] += dp[val]
            dp[val] = 0
        dq[tmp] += 1
        ans += dq[0] 
    
print(ans)

Solution (Python):
def main():
    *s, = map(int, input())  

    r = [0] * 2019
    r[0] = 1

    ans = 0

    t = 0
    p = 1
    for x in reversed(s):
        t = (t + x * p) % 2019
        p = (p * 10) % 2019
        ans += r[t]
        r[t] += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

S = input()
N = len(S)

M = []
cum = [0]

ans = 0

for i in range(N):
    M.append(pow(10, i, 2019) * int(S[-1 - i]) % 2019)

for i in range(N):
    cum.append((cum[-1] + M[i]) % 2019)

C = Counter(cum)

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

print(ans)

Solution (Python):
S = input()
from collections import defaultdict
d = defaultdict(lambda:0)
N = len(S)
s = 0
p = [1]*N
for i in range(N):
    p[i] = p[i-1]*10%2019

for i in range(N-1,-1,-1):
    s += int(S[i])*(p[N-1-i])
    s %= 2019
    d[s] += 1
ans = 0
for k in d:
    n = d[k]
    ans += (n*(n-1))//2
ans += d[0]
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = list(map(int, list(input())))[::-1]

l = [0]*2019

tmp = 0
z = 1
for i, s in enumerate(S):
	tmp += s*z
	z = z*10%2019
	l[tmp%2019] += 1
ans = 0
for v in l:
	ans += v*(v-1)//2
print(ans+l[0])

Solution (Python):
S = input()



def power_func(a, n, p):
    res = 1 
    while n > 0:
        if n & 1:
            res = res * a % p
        a = a * a % p 
        n = n >> 1
    return res

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


import collections
dct = dict(collections.Counter(Q))

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

Solution (Python):
S = input()
N = len(S)
mod = 2019
X = [0 for _ in range(N)]
base = 1
for i in range(N, 0, -1):
    X[i-1] = ((int(S[i-1]) * base) % mod)
    base *= 10
    base %= mod
for i in range(1, N):
    X[i] += X[i-1]
    X[i] %= mod
D = {i: 0 for i in range(mod)}
for i in range(N):
    D[X[i]] += 1
XX = 0
for i in D:
    if i != 0:
        XX += (D[i] * (D[i] - 1)) // 2
    else:
        XX += (D[0] * (D[0] + 1)) // 2
print(XX)

Solution (Python):
S = [int(i) for i in list(input())]
S.reverse()
l = len(S)
T = [0]
for i in range(l):
    T.append((T[-1]+S[i]*(pow(10, i, 2019))) % 2019)
C = {}
for t in T:
    try:
        C[t] += 1
    except:
        C[t] = 1
ans = 0
for c in C.values():
    ans += c*(c-1)//2
print(ans)

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

ans = 0

if P in (2, 5):
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i + 1
else:
    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
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    S = [int(s) for s in list(input().strip())][::-1]
    N,P = len(S), 2019
    
    num = 0
    ans = 0
    
    if P == 2 or P == 5:
    	for i in range(N):
    		if S[i] % P == 0:
    			ans += N-i
    	print(ans)
    	return

    L = [0] * P
    L[0] = 1
    t = 0
    s = 1
	
    for z in S:
    	t = (z * s + t)%P	
    	L[t]+=1
    	s = s * 10 % P
	
    for l in L:
    	ans += l * (l - 1) // 2
    
    print(ans)


if __name__ == '__main__':
	main()

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
S = list(map(int, list(input())[: -1]))
N = len(S)
P = 2019
rcs = [0] * (N + 1)
for i in range(N, 0, -1): rcs[i - 1] = (rcs[i] + S[i - 1] * pow(10, N - i, P)) % P

d = dd(list)
for i in range(N + 1):d[rcs[i]].append(i)
res = 0
if P == 2 or (P == 5):
  for i in range(N - 1, -1, -1):
    res += (S[i] % P == 0) * (i + 1)
  print(res)
  exit(0)
table = [0] * P
for i in range(N, -1, -1):
  x = rcs[i]
  res += table[x]
  table[x] += 1
print(res)

Solution (Python):
S = list(map(int, input()[::-1]))

R=[0]
r=0
k=1
for c in S:
    r = (r+k*c) % 2019
    k = k*10 % 2019
    R.append(r)
    
N = [0]*2019
ans = 0
for r in R:
    ans += N[r]
    N[r] += 1
print(ans)

Solution (Python):
s = list(map(int, input()))
n = len(s)
p = 2019
ans = 0

s.reverse()
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = (cum[i] + s[i] * pow(10, i, p)) % p
t = [0] * p
for x in cum: t[x] += 1

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

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    s = input()
    l = len(s)

    from collections import Counter
    counter = Counter()
    prev = 0
    counter[0] += 1

    for i in range(l):
        num = int(s[l - i - 1])
        m = (num * pow(10, i, 2019) + prev) % 2019
        counter[m] += 1
        prev = m

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

    print(ans)


if __name__ == '__main__':
    main()

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

Solution (Python):
def main():
    S = input()
    u = 0
    H = [0] * 2019
    H[0] = 1
    m = 1
    r = 0
    for s in reversed(S):
        u = (u + m * int(s)) % 2019
        r += H[u]
        H[u] += 1
        m = (m * 10) % 2019
    return r


print(main())

Solution (Python):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
S=list(reversed(input()))
lst=[0 for i in range(len(S))]
num=0
z=1
for i in range(len(S)):
    num+=int(S[i])*z
    num%=2019
    z*=10
    z%=2019
    lst[i]=num
lst=Counter(lst)
lst[0]+=1
count=0
for l in lst:
    n=lst[l]
    count+=n*(n-1)//2
print(count)

Solution (Python):
from collections import Counter
s = input()
leng = len(s)
cnt = 0
mod = 2019

SUM = [0] * (leng + 1)
for i in range(leng):
    temp = int(s[-(i + 1)]) * pow(10, i, mod)
    SUM[i + 1] = (SUM[i] + temp) % mod


ans = Counter(SUM)
for i in ans.values():
    if i >= 2:
        cnt += i * (i - 1) // 2
print(cnt)

Solution (Python):

import sys
from collections import Counter


INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S):
    
    L = 2019
    rl = [0] * L
    rl[0] = 1
    ans = 0
    for c in S:
        n = int(c)
        nrl = [0] * L
        nrl[0] = 1
        for r in range(L):
            m = rl[r]
            r = (r * 10 + n) % 2019
            if r == 0:
                ans += m
            nrl[r] += m
        rl = nrl
        

    return ans


def main():
    S = read_str()
    print(slv(S))

    
    
    


if __name__ == '__main__':
    main()

Solution (Python):
mod = 2019
eps = 10**-9


def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    S = input().rstrip('\n')
    S = S[::-1]
    N = len(S)
    CS = [0] * (N+1)
    for i in range(N):
        CS[i+1] = (CS[i] + (int(S[i]) * pow(10, i, mod))%mod)%mod
    dic = defaultdict(int)
    for a in CS:
        dic[a] += 1
    ans = 0
    for v in dic:
        a = dic[v]
        ans += a * (a-1) // 2
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
s=input()[::-1]
n=len(s)
a=[0]*2019
a[0]=1
x=1
p=0

for i in range(n):
    p+=x*int(s[i])
    p%=2019
    a[p]+=1
    x=(x*10)%2019
ans=0
for i in range(2019):
    ans+=a[i]*(a[i]-1)//2
print(ans)

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

n = len(s)

l_sum = [0]
for i in range(n):
    x = (l_sum[-1] + int(s[n-i-1]) * (pow(10, i, 2019))) % 2019
    l_sum.append(x)


l_sum.sort()
ans = 0
tmp = 0
cnt = 1
for i in range(1, len(l_sum)):
    if l_sum[i] == tmp:
        cnt += 1
    else:
        ans += cnt * (cnt - 1) // 2
        cnt = 1
        tmp = l_sum[i]

ans += cnt * (cnt - 1) // 2
print(ans)

Solution (Python):

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

def main():
    mod=2019
    S=list(input())
    S=S[::-1]
    N=len(S)
    
    from collections import defaultdict
    dd = defaultdict(int)
    
    p=[1]*N
    for i in range(N-1):
        p[i+1]=(p[i]*10)%mod
    
    now=0
    dd[0]=1
    for i in range(N):
        now=now+int(S[i])*p[i]
        now%=mod
        dd[now]+=1
        
    ans=0
    for k,v in dd.items():
        ans+=(v*(v-1))//2
    print(ans)
    

main()