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()
size = len(S)
L = [0] * 2019

tmp = int(S[size - 1])  
L[0] = 1
L[tmp] += 1
tmp_r = 1  

for i in reversed(range(size - 1)):  
    n = int(S[i])  
    tmp_r = (tmp_r*10) % 2019
    r = (n * tmp_r) % 2019
    tmp = (tmp + r) % 2019
    
    L[tmp] += 1

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


def calc(i):
    if (i == 0):
        return


print(ans)

Solution (Python):
from collections import Counter


s = input()

n = len(s)
DP = [0] * (n + 1)

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

COUNTS = Counter(DP)

print(sum(count * (count - 1) // 2 for count in COUNTS.values()))

Solution (Python):
def resolve():
    s = input()
    s = s[::-1]
    c = [0]*2019
    
    c[0] = 1
    r = 0
    d = 1
    for i in s:
        num = int(i) * d % 2019 + r
        num %= 2019
        c[num] += 1
        r = num
        d *= 10
        d %= 2019
    ans = 0
    for i in c:
        ans += i*(i-1)//2
    print(ans)
resolve()

Solution (Python):
s = input()[::-1]
mod = 2019
cnt = [0] * mod
x = 1
cnt[0] = 1
total = 0
for s in s:
    total += int(s) * x
    total %= mod
    cnt[total] += 1
    x *= 10
    x %= mod


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

Solution (Python):
s = input()
line = s[::-1]
n = len(s)
mods = [1] + [0] * 2018
i = 1
now = 0
for d in line:
    now += int(d) * i
    now %= 2019
    mods[now] += 1
    i *= 10
    i %= 2019

ans = 0
for mod in mods:
    ans += mod*(mod-1) / 2

print(int(ans))

Solution (Python):
s = input()[::-1]
m = 2019
ans = 0
x = 1
tot = 0
cnt = [0] * m
cnt[0] = 1
for s in s:
    tot += int(s) * x
    tot %= m
    
    x *= 10
    x %= m
    cnt[tot] += 1

print(sum(i*(i-1)//2 for i in cnt))

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

n=len(s)
D=[0]*(n+1)
c=[0]*(n+1)
ans = 0
f = 0
dp = [0]*(2020)
dp[0]+=1
tmp =0
x = 1
for e,i in enumerate(s):
    tmp = (tmp+x*i)%2019
    ans += dp[tmp]
    dp[tmp]+=1
    x = x*10 %2019
print(ans)

Solution (Python):
s=input()[::-1]
mod=[0]*2019
mod[0]=1
x=1
num=0
ans=0

for t in s:
    num += int(t) * x
    num %= 2019
    x *= 10
    x %= 2019
    mod[num] +=1

for u in mod:
    ans += u*(u-1)//2

print(ans)

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

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

num, d = 0, 1

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

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

print(ans)

Solution (Python):
s = list(map(int, input()))[::-1]
mods = [0] * 2019
mods[0] = 1

v = 0
d = 1
for n in s:
    v = (v + n * d) % 2019
    d = (d * 10) % 2019

    mods[v] = mods[v] + 1

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

Solution (Python):
number = str(input())[::-1]
remainderDictionary = {0: 1}
digitDictionary = {'1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}

sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum = (sum + digitDictionary[i] * x) % 2019 
  remainderDictionary[sum] = remainderDictionary.get(sum,0) + 1

ansDictionary = {} 
ans = 0
for i in remainderDictionary:
  remainderOccurences = remainderDictionary[i]
  value = ansDictionary.get(remainderOccurences,-1)
  if value == -1:
    value = remainderOccurences * (remainderOccurences - 1) // 2 
    ansDictionary[remainderOccurences] = value
  ans += value
print(ans)

Solution (Python):
number = str(input())[::-1]
remainderDictionary = {0: 1}
digitDictionary = {'1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}

sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum = (sum + digitDictionary[i] * x) % 2019 
  remainderDictionary[sum] = remainderDictionary.get(sum,0) + 1

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

Solution (Python):

import sys,bisect,math
sys.setrecursionlimit(15000)

s = sys.stdin.readline().rstrip()
cum = [0]*(len(s)+1)
import collections
d = collections.defaultdict(int)
d[0] = 1
ret = 0
dig = 1
for i in range(len(s))[::-1]:
    cum[i]=(int(s[i])*dig+cum[i+1])%2019
    dig = (dig*10)%2019
    
    if cum[i] in d:
        ret += d[cum[i]]
    d[cum[i]] += 1

print(ret)

Solution (Python):
number = str(input())[::-1]
remainderDictionary = {0: 1}
digitDictionary = {'1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}

sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum = (sum + digitDictionary[i] * x) % 2019 
  remainderValue = remainderDictionary.get(sum,0) + 1
  remainderDictionary[sum] = remainderValue
     
ans = 0
for i in remainderDictionary:
  value = remainderDictionary[i]
  if value > 1:
    ans += value * (value - 1) // 2 
print(ans)

Solution (Python):
number = str(input())[::-1]
remainderDictionary = {0: 1}
digitDictionary = {'1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}

sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum = (sum + digitDictionary[i] * x) % 2019 
  remainderValue = remainderDictionary.get(sum,0) + 1
  remainderDictionary[sum] = remainderValue
     
ans = 0
for i in remainderDictionary:
  value = remainderDictionary[i]
  ans += value * (value - 1) // 2 
print(ans)

Solution (Python):
number = str(input())[::-1]
remainderDictionary = {0: 1}

digitDictionary = {'0':0, '1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}

sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum = (sum + digitDictionary[i] * x) % 2019 
  remainderValue = remainderDictionary.get(sum,0) + 1
  remainderDictionary[sum] = remainderValue
     
ans = 0
for i in remainderDictionary:
  value = remainderDictionary[i]
  ans += value * (value - 1) // 2 
print(ans)

Solution (Python):
number = str(input())[::-1]
remainderDictionary = {0: 1}
    
sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum = (sum + int(i) * x) % 2019 
  remainderValue = remainderDictionary.get(sum,0) + 1
  remainderDictionary[sum] = remainderValue
     
ans = 0
for i in remainderDictionary:
  value = remainderDictionary[i]
  ans += value * (value - 1) // 2 
print(ans)

Solution (Python):
number = str(input())[::-1]
remainderDictionary = {0: 1}
    
sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum += int(i) * x
  sum %= 2019
  remainderValue = remainderDictionary.get(sum,0) + 1
  remainderDictionary[sum] = remainderValue
     
ans = 0
for i in remainderDictionary:
  value = remainderDictionary[i]
  ans += value * (value - 1) // 2 
print(ans)

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

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

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

print(ans)

Solution (Python):

S = list(map(int, reversed(input())))

"""
「2019の倍数か」は「mod 2019 が 0 になるか」と同意。
しかし、普通に切り出して、１つずつチェックすると計算工数がかかるので、累積和を使う。
各桁の値を （桁の数値a_k）× 10^k と表現し、mod 2019 の値を予め計算し、累積和を作っておく。
ここで、10^k の部分は、2019と互いに疎（公約数がない）なので、
含めて計算しても mod 2019 の周期を乱さない。（勿論オフセットは変わる）
「(i, j) が2019で割り切るか」は、「i～j の累積和が同じ値になる（2019周期）か」と同意。
累積和が同じ値になる個数を数えて、組み合わせを計算すればよい。
"""

a = [0] * len(S)

sums = [0] * (len(S) + 1)

d = 1

cnt = [0] * 2019
cnt[0] = 1  
for i in range(len(S)):
    a[i] = (S[i] * d) % 2019
    sums[i + 1] = (sums[i] + a[i]) % 2019
    d = (d * 10) % 2019 
    cnt[sums[i + 1]] += 1


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

Solution (Python):
s = input()[::-1]
v = 0
mods = {}
mods[0] = 1
d = 1

for c in s:
    v += int(c) * d
    
    v %= 2019
    d *= 10
    d %= 2019
    try:
        mods[v] += 1
    except KeyError:
        mods[v] = 1

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

print(ans)

Solution (Python):
S = input()

X = [0]*2019
X[0] = 1
d = 1
a = 0

for s in reversed(S):
    a = ((ord(s) - ord('0'))*d + a)%2019
    d = d*10%2019
    X[a] += 1

ans = sum(x*(x-1)//2 for x in X)
print(ans)

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

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

num, d = 0, 1

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

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

print(ans)

Solution (Python):
s = input()
table = [0 for i in range(2019)]
table[0] = 1
num = 0
d = 1
for c in s[::-1]:
    num += (int(c) * d)
    num %= 2019
    d *= 10
    d %= 2019
    table[num] += 1

ans = 0
for cnt in table:
    ans += cnt * (cnt - 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()[::-1]

cnts = [1] + [0] * (2019 - 1)
tmp = 0
d = 1

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

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

print(ans)

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

cnts = [1] + [0] * (2019 - 1)
tmp = 0
d = 1

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

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

print(ans)

Solution (Python):
import collections
import math

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

def naive(s):
	cnt = 0
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			k = int(s[i:j])
			if k % 2019 == 0 and k != 0:
				
				cnt += 1
	return cnt

def main(s):
	nums = [0]
	cur = 0
	p = 0.1
	for i in range(len(s)):
		p = int(p * 10) % 2019
		cur = (cur + int(s[len(s) - 1 - i]) * p) % 2019
		nums.append(cur)
	d = dict(collections.Counter(nums))
	a = [val for key, val in d.items() if val >= 2]
	return sum([comb(x, 2) for x in a])	

s = input()
print(main(s))

Solution (Python):
S = input()[::-1]
Surpus = [0] * 2019
Surpus[0] = 1

sum = 0
x = 1
for i in S:
    sum += int(i) * x
    Surpus[sum % 2019] += 1
    x *= 10
    x %= 2019

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

print(ans)

Solution (Python):
mods = [0]*2019
mods[0] = 1
s = input()
t = 0
u = 1
for i in range(1,len(s)+1):
    t = (t + int(s[-i])*u)%2019
    u = u*10%2019
    mods[t] += 1


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)/2
print(int(cnt))

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

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




counter = [0] * 2019
k = 10
for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        sub += int(S[N - i]) * k
        k *= 10
        k %= 2019
    rest = sub % 2019
    counter[rest] += 1

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

Solution (Python):
s = input()
n = len(s)
power = [0]*(n+1)
power[-1] = 1
x = 1
for i in range(n-1,-1,-1):
	x = (x*10) % 2019
	power[i] = x
mod19 = [0]*(n+1)
cnt = [0]*2020
cnt[0] = 1
x=0
mod19[n] = 0
for i in range(n-1, -1,-1):
	x = (x+int(s[i])*power[i])%2019
	mod19[i] = x
	cnt[x]+=1
ans = 0
for i in range(2020):x = cnt[i];ans+= x*(x-1)//2
print(ans)

Solution (Python):
s = list(input())
n = len(s)
mod = 2019

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

count = [0]*mod
for i in range(n+1):
    count[d[i]] += 1

ans = 0
for i in range(mod):
    c = count[i]
    ans += c*(c-1) // 2

print(ans)

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

int1 = lambda x: 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)]
 
INF = float('inf')
 
def solve():
    S = list(map(int, list(input())))
 
    S = S[::-1]
    
    n = len(S)
    mod = 2019
 
    
    A = [0] * (n)
    a = 1
    for i in range(n):
        A[i] = S[i] * a
        a = a * 10 % mod
    
 
    
    R = [0] * (n+1)
    for j in range(n):
        R[j+1] = (R[j] + A[j]) % mod
    
 
    
    cnt = {}
    ans = 0
    for l in range(0, n+1):
        r = R[l]
        ans = ans + cnt.get(r, 0)
        cnt[r] = cnt.setdefault(r, 0) + 1
    print(ans)
 
if __name__ == '__main__':
    solve()

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

int1 = lambda x: 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)]
 
INF = float('inf')
 
def solve():
    S = list(map(int, list(input())))
 
    S = S[::-1]
    
    n = len(S)
    mod = 2019
 
    
    A = [0] * (n)
    a = 1
    for i in range(n):
        A[i] = S[i] * a
        a = a * 10 % mod
    
 
    
    R = [0] * (n+1)
    for j in range(n):
        R[j+1] = (R[j] + A[j]) % mod
    
 
    
    cnt = {}
    ans = 0
    for l in range(0, n+1):
        r = R[l]
        ans = ans + cnt.get(r, 0)
        cnt[r] = cnt.setdefault(r, 0) + 1
    print(ans)
 
if __name__ == '__main__':
    solve()

Solution (Python):
N = input()
num = len(N)
mod_sum = [0]*2019
mod_sum[0] = 1
ans = 0
a = 0
d = 1
for i in range(num):
  a = (a + int(N[-i-1])*d)%2019
  d = (d*10)%2019
  mod_sum[a] += 1
for i in mod_sum:
  ans += i*(i-1)//2
print(ans)

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

    count = 0

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

    print(count)

if __name__ == '__main__':
    main()

Solution (Python):


s = input()


pow = [1]
while len(pow) <= 1 or pow[-1] > 1:
    pow.append(pow[-1] * 10 % 2019)
n = len(pow) - 1  


memo = [[0] * 2019 for i in range(n)]
memo[n - 1][0] = 1  

count = 0  
mod = 0
for j, c in enumerate(s):
    mod = (mod * 10 + int(c)) % 2019  
    for i in range(1, n + 1):
        m = mod * pow[n - i] % 2019  
        count += memo[(j - i + n) % n][m]
    memo[j % n][mod] += 1

print(count)

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

d = [0] * (n+1)

k = 1
for i in range(n):
    d[i+1] = d[i] + k * int(s[n-1-i])
    d[i+1] %= mod
    k *= 10
    k %= mod

count = [0] * mod
for i in range(n+1):
    count[d[i]] += 1

ans = 0
for i in range(mod):
    c = count[i]
    ans += c * (c-1) // 2

print(ans)

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


power = [0] * len_S
power[len_S - 1] = 1

for i in range(1,len_S):
    power[len_S-i-1] = (power[len_S-i] * 10) % mod

a = []
S_a = [0] * len_S
for i in range(len_S):
    a.append((power[i] * int(S[i])) % mod)
    if i > 0:
        S_a[i] = S_a[i-1] + int(a[i])
    else:
        S_a[i] = int(a[i])


cnt = [0] * 2020
ans = 0
for i in range(len_S):
    cnt[S_a[i]%mod] += 1


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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

MOD = 2019

def solve(S):
    dp = np.zeros(MOD, np.int64)
    temp = np.empty_like(dp)
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % MOD
        temp[x:] = dp[:-x]
        temp[:x] = dp[-x:]
        dp, temp = temp, dp
        answer += dp[0]
        pow10 *= 10
        pow10 %= MOD
    return answer


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i4[:],)')(solve)
    cc.compile()

if sys.argv[-1] == 'ONLINE_JUDGE':
    cc_export()
    exit()
else:
    from my_module import solve

S = np.array(list(read().rstrip()), dtype=np.int32) - ord('0')
print(solve(S))

Solution (Python):
s = input()
n = len(s)
power = [0]*(n+1)
power[-1] = 1
x = 1
for i in range(n-1,-1,-1):
	x = (x*10) % 2019
	power[i] = x
mod19 = [0]*(n+1)
cnt = [0]*2020
x=0
for i in range(n, 0,-1):
	x = (x+int(s[i-1])*power[i])%2019
	mod19[i] = x
	cnt[x]+=1
ans = 0
for i in range(2020):x = cnt[i];	ans+= x*(x-1)//2
print(ans+cnt[0])

Solution (Python):
s = input()

n = len(s)

power = [0]*(n+1)
power[-1] = 1
x = 1

for i in range(n-1,-1,-1):
	x = (x*10) % 2019
	power[i] = x
	
mod19 = [0]*(n+1)

cnt = [0]*2020

x=0
for i in range(n, 0,-1):
	x = (x+int(s[i-1])*power[i])%2019
	mod19[i] = x
	cnt[x]+=1
	


	
ans = 0

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

	
print(ans+cnt[0])

Solution (Python):
from itertools import permutations, accumulate
mod = 2019

a = list(map(int,input()))
n = len(a) 

for i in range(n):
    a[i] *= pow(10,n-i-1,mod) 
    
s = [0]+list(accumulate(a)) 
d = [0]*mod
ans = 0
for i in s:
    j = i%mod
    ans += d[j]
    d[j] += 1
print(ans)

Solution (Python):
s= input()[::-1]
mods= [0] * 2019
mods[0] = 1
num=0
d = 1
for c in s:
    num += int(c) * d
    num %= 2019
    d *= 10
    d %= 2019
    mods[num] += 1

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

print(ans)

Solution (Python):
n = input()
l = len(n)
s = [0] * 2020
m = [0] * (l+1)
m[0] = 1
s[0] = 1
for i in range(1, l+1):
    m[i] = (m[i-1]*10) % 2019
tmp = 0
n = list(n)[::-1]
for i in range(len(n)):
    
    tmp = (tmp + int(n[i])*m[i]) % 2019
    
    s[tmp] += 1
su = 0
for i in s:
    if i > 1:
        
        su += i * (i - 1)//2
print(su)

Solution (Python):
INT_MAX=10**11+7
MOD=10**9+7
def INPUT():return list(int(i) for i in input().split())
def LIST_1D_ARRAY(n):return [0 for _ in range(n)]
def LIST_2D_ARRAY(m,n):return [[0 for _ in range(n)]for _ in range(m)]

s=input()
digits=list(int(i) for i in s)
n=len(s)
powermod=[0]*2019
powermod[0]=1
pow10=1
num=0
ans=0
for digit in reversed(digits):
    num+=digit*pow10
    rem=num%2019
    ans+=powermod[rem]
    pow10*=10
    powermod[rem]+=1
    num=rem
    pow10%=2019
print(ans)

Solution (Python):
N = 2019
cnt = [0] * N
S = input()
ans = 0
for s in S:
    s = int(s)
    new = [0] * N
    for n in range(N):
        idx = (10 * n + s) % N
        new[idx] += cnt[n]
    cnt = new
    cnt[s] += 1
    ans += cnt[0]

print(ans)

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

target = 2019



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

num, d = 0, 1
digit = 1
mod = 0
for c in original:
    
    
    
    
    
    
    num += int(c) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1



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

print(ans)

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

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

num, d = 0, 1

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

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

print(ans)

Solution (Python):
S = input()
n = len(S)
dp = [0 for _ in range(n+1)]
count = [0 for _ in range(2019)]
count[0] = 1
p=1
for i in range(1,n+1):
    dp[i] = (dp[i-1]+int(S[n-i])*p) % 2019
    p = p*10%2019
    count[dp[i]] += 1

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

print(int(sum(count)))

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

r = 0
C = [0 for _ in range(MOD)]
C[0] = 1

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

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

print(int(a))

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

dp = [0]*2019
dp[0]=1
total = 0
a = 1

for i in list(s):
  total += int(i)*a
  total %= 2019
  dp[total] += 1
  a *= 10
  a %= 2019
count=0
  
for i in range(2019):
    count += dp[i]*(dp[i]-1)//2
 
print(count)

Solution (Python):
def main():
    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)
    

if __name__=="__main__":
    main()

Solution (Python):
N = 2019


def main():
    S = input()
    mod = [0] * N
    ans = 0
    for c in S:
        nxt = [0] * N
        x = int(c)
        for i in range(N):
            nxt[(i*10+x) % N] += mod[i]
        nxt[x] += 1
        ans += nxt[0]
        mod = nxt
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys


def solve(S: str):
    T = [0 for _ in range(len(S) + 1)]
    for i in range(len(S) - 1, -1, -1):
        T[i] = (T[i+1] + int(S[i]) * pow(10, len(S) - 1 - i, 2019)) % 2019
    
    M = [0 for _ in range(2019)]
    
    for t in T:
        M[t] += 1
    ct = 0
    for m in M:
        ct += m * (m - 1) / 2

    print(int(ct))
    return



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

if __name__ == '__main__':
    main()

Solution (Python):




P=2019


S,a,i,j,c=input(),0,0,1,[1]+[0]*P
if 10%P:
	for v in S[::-1]:i,j=(i+int(v)*j)%P,j*10%P;a+=c[i];c[i]+=1
else:
	for v in S:
		i+=1
		if int(v)%P<1:a+=i
print(a)

Solution (Python):
S = input()[::-1]
 
cnt = [0] * 2019
cnt[0] = 1
total = 0
x = 1
ans = 0
 
for a in S:
    total += int(a) * x
    total %= 2019
    cnt[total] += 1
    x = x*10
    x %= 2019
 
for i in range(2019):
    ans += cnt[i]*(cnt[i]-1)//2
 
print(ans)

Solution (Python):
s=input()
s=s[::-1]
a=1
b=0
t=[0]*2019
t[0]=1
ans=0
for i in range(len(s)):
    b+=int(s[i])*a
    b%=2019
    a*=10
    ans+=t[b]
    t[b]+=1
    a%=2019

print(ans)

Solution (Python):
S = input()[::-1]
 
cnt = [0] * 2019
cnt[0] = 1
total = 0
x = 1
ans = 0
 
for a in S:
    total += int(a) * x
    total %= 2019
    cnt[total] += 1
    x = x*10
    x %= 2019
 
for i in range(2019):
    ans += cnt[i]*(cnt[i]-1)//2
 
print(ans)

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

m = 2019
cnt = [0] * m
cnt[0] = 1
total = 0
x = 1
ans = 0

for i in range(len(S)):
    total += int(S[i])*x
    total %= m
    cnt[total] += 1
    x = 10*x
    x %= m

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

print(ans)

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

Solution (Python):





import numpy as np
S = input()
cand = np.zeros(2019,dtype=int)
rem = 0
order = 1
mod = 2019
for s in S[::-1]:
    rem += (int(s)*order)%mod
    rem %= mod
    cand[rem] +=1
    order *= 10
    order %=mod
ans = cand[0]
cand = cand[cand>1]
for c in cand:
    ans += c*(c-1)/2
print(int(ans))

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

Solution (Python):
from collections import Counter

s=input()[::-1]
ans=0
lst=[0]
num=0
p=1
for i in s:
    lst.append((int(i)*p+lst[-1])%2019)
    p=p*10%2019

ans=sum(x*(x-1)//2 for x in Counter(lst).values())
print(ans)

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *
































def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007




def main():
	S = inputStr()
	S = S[::-1]

	dol = {0:1}
	tmptmp = 0
	kinou = 0
	for i,val in enumerate(S):

		if tmptmp == 0:
			tmptmp = 1
		else:
			tmptmp = tmptmp * 10 % 2019
		tmp = (int(val) * tmptmp) % 2019
		tmp = (tmp + kinou) % 2019
		kinou = tmp

		if tmp in dol:
			dol[tmp] += 1
		else:
			dol[tmp] = 1

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

	
	print(ans)





def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

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

tmp_amari = [0]*2019


num = 0
order = 1
for i in s:
    num += int(i)*order
    num %= 2019
    
    tmp_amari[num] += 1
    order *= 10
    order %= 2019
    

tmp_print = [i for i in tmp_amari if i > 0]


ans = 0
ans += tmp_amari[0]

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

print(ans)

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *




























def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007




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

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

	num, d = 0, 1

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

		ans = 0

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

	print(ans) 





def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Solution (Python):

"""
：余りの等しい物をカウントし、その累積和
：Aの余りとBの余り(mod 2019)が等しい場合
　A-Bは2019の倍数である
：計算量を抑えるため各項と１０の指数乗は分けて計算する
：
"""

import sys
input=sys.stdin.readline
s = input()[:-1][::-1] 

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

num, d = 0, 1

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

ans = 0

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

print(ans)

Solution (Python):
def main():
    s=list(input())[::-1]
    ans,tot,x,m=0,0,1,2019
    cnt=[0]*m
    n=len(s)
    for i in range(n):
        cnt[tot] += 1
        tot += int(s[i])*x
        tot %= m
        ans += cnt[tot]
        x = x*10%m
    print(ans)

if __name__ == '__main__':
    main()

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

arr = [0]*2019
arr[0] += 1
count = 0
dig = 1
r = 0

for i in range(0,n):
  r = (r + int(st[i]) * dig) % 2019
  arr[r] += 1
  dig = dig * 10 % 2019

for i in arr:
  count += i*(i-1)//2;

print(count)

Solution (Python):
def main():
    A = input()[::-1]
    A = "0" + A
    

    

    
    S = [0] * len(A)
    cnt = [0] * 2019
    cnt[0] = 1

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

    

    
    

    ans = 0

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

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
S = input()[::-1]
N = len(S)
sum_of_mod = [0] * 2019
sum_of_mod[0] += 1
digit = 1
now = 0
for i in range(N):
    now = int(S[i])*digit + now
    now %= 2019
    digit *= 10
    digit %= 2019
    sum_of_mod[now] += 1

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

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

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

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1
    
ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans)

Solution (Python):
import sys
import numpy as np

def solve(S):
	M = 2019
	t = 1
	ans = 0
	c = np.zeros(M, dtype=np.int64)
	c[0] = 1
	r = 0
	for d in S:
		r = (d * t + r) % M
		ans += c[r]
		c[r] += 1
		t = t * 10 % M
	return ans



def cc_export():
	from numba.pycc import CC
	cc = CC('my_module')
	cc.export('solve', 'i8(i4[:])')(solve)
	cc.compile()

if __name__ == '__main__':
	import sys
	if sys.argv[-1] == 'ONLINE_JUDGE':
		cc_export()
		exit(0)
	from my_module import solve
	S = sys.stdin.buffer.readline().decode('utf-8').rstrip()
	S = np.array([int(d) for d in S[::-1]], dtype=np.int32)
	print(solve(S))