Problem: 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.

Submission attempts (in order):
import math
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)


S = readChar()

res = [0]*len(S)
res[-1]=int(S[-1])

d = defaultdict(int)

for i in range(2,len(S)+1):
	re = int(S[i*-1])*pow(10,i-1,2019)
	d[(res[i*-1+1]+re)%2019]+=1

ans = d[0]
for key in d:
	if d[key]>1:
		ans+=comb(d[key],2)

print(ans)

p=d=2019
z=[0]*p
for i,j in enumerate(input()[::-1]):
	d=d+int(j)*pow(10,i,p)
	z[d%p]+=1
r=z[0]
for i in a:
	r+=i*(i-1)//2
print(r)

import math

def readInt():
	return int(input())

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

def readChars():
	return input().split()

s = input()

ai = [0]*len(s)
si = [0]*len(s)

p = 2019

import math
import queue

def readInt():
	return int(input())

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

def readChars():
	return input().split()

def sumDigits3(s):
	x = list(s)
	y = [int(i) for i in x]
	return sum(y)%3==0

def mod(a,b,n):
	return (a-b)/pow(10*n)%2019

s = input()

ai = [0]*len(s)
si = [0]*len(s)

for i in range(len(s)):
	print(s[i])
	ai[len(s)-i-1] = (int(s[-1*i-1])*pow(10,i))%3
for i in range(len(ai)):
	si[i] = sum(ai[0:i])

res = 0
for i in range(2019):
	c = si.count(i)
	res += c*(c-1)/2

print(res)

import math

def readInt():
	return int(input())

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

def readChars():
	return input().split()

s = input().reverse()

ai = [0]*len(s)
si = [0]*len(s)

p = 2019

for i in range(len(s)):
	(int(s[i])*pow(10,i))%p

import math

def readInt():
	return int(input())

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

def readChars():
	return input().split()

s = input()

ai = [0]*len(s)
si = [0]*len(s)

p = 2019

for i in range(len(s)):
	ai[i] = (int(s[i])*pow(10,i))%p

import math

def readInt():
	return int(input())

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

def readChars():
	return input().split()

s = reversed(input())

ai = 0
si = [0]*len(s)

p = 2019

for i, j in enumerate(s):
	ai = (int(j)*pow(10,i,p))%p
	si[i] = (si[i-1]+ai)%p
countarr = [0]*2019
for i in si:
	countarr[i]+=1

res = countarr[0]
for i in range(p):
	c = countarr[i]
	res += c*(c-1)//2

print(res)

import math

def readInt():
	return int(input())

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

def readChars():
	return input().split()

s = input()

ai = [0]*len(s)
si = [0]*len(s)

p = 2019

for i in range(len(s)):
	ai[i] = (int(s[-1*i-1])*pow(10,i))%p

import math

def readInt():
	return int(input())

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

def readChars():
	return input().split()

s = input()[::-1]

ai = [0]*len(s)
si = [0]*len(s)

p = 2019

for i in range(len(s)):
	(int(s[i])*pow(10,i))%p

import math
import queue

def readInt():
	return int(input())

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

def readChars():
	return input().split()

def sumDigits3(s):
	x = list(s)
	y = [int(i) for i in x]
	return sum(y)%3==0

def mod(a,b,n):
	return (a-b)/pow(10*n)%2019

s = input()

ai = [0]*len(s)
si = [0]*len(s)

for i in range(len(s)):
	ai[len(s)-i-1] = (int(s[-1*i-1])*pow(10,i))%3
for i in range(len(ai)):
	si[i] = sum(ai[0:i])

res = 0
for i in range(2019):
	c = si.count(i)
	res += c*(c-1)//2

print(res)

import math

def readInt():
	return int(input())

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

def readChars():
	return input().split()

s = input().reverse()

ai = [0]*len(s)
si = [0]*len(s)

p = 2019
ee = 0
for i in range(len(s)):
	ee = (int(s[i])*pow(10,i))%p

import math

def readInt():
	return int(input())

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

def readChars():
	return input().split()

s = input()

ai = [0]*len(s)
si = [0]*len(s)

p = 2019

for i in range(len(s)):
	ai[i] = (int(s[-1*i-1])

p=2019
s,a,d,z=reversed(input()),0,0,[0]*p
for i in range(len(s)):
	d=(d+(int(s[i])*pow(10,i,p)))%p
	z[d]+=1
r=z[0]
for i in range(p):
	r+=z[i]*(z[i]-1)//2
print(r)

p=2019
z=[0]*p
s,a,d,r=reversed(input()),0,0,z[0]
for i,j in enumerate(s):
	d=(d+(int(j)*pow(10,i,p)))%p
	z[d]+=1
for i in range(p):
	r+=z[i]*(z[i]-1)//2
print(r)

import math

def readInt():
	return int(input())

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

def readChars():
	return input().split()

s = input()

ai = [0]*len(s)
si = [0]*len(s)

p = 2019

for i in range(len(s)):
	ai[i] = (int(s[-1*i-1]))

import math

def readInt():
	return int(input())

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

def readChars():
	return input().split()

s = reverse(input())

ai = [0]*len(s)
si = [0]*len(s)

p = 2019

for i in range(len(s)):
	ai[i] = (int(s[i])*pow(10,i))%p
	si[i] = sum(ai[:i+1])%p
countarr = [0]*2019
for i in si:
	countarr[i]+=1

res = countarr[0]
for i in range(p):
	c = countarr[i]
	res += c*(c-1)//2

print(res)

import math

def readInt():
	return int(input())

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

def readChars():
	return input().split()

s = input()

ai = [0]*len(s)
si = [0]*len(s)

p = 2019

for i in range(len(s)):
	ai[i] = (int(s[-1*i-1])*pow(10,i))%p
	si[i] = sum(ai[:i+1])%p
countarr = [0]*2019

import math
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)


S = readChar()

res = [0]*len(S)
res[-1]=int(S[-1])

d = defaultdict(int)

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


for i in res:
	d[i]+=1

ans = d[0]
for key in d:
	if d[key]>1:
		ans+=comb(d[key],2)

print(ans)

Verdicts: Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Accepted