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.



Sample input:
1817181712114


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
inp = input()

s = 0

for i in range(len(inp)-3):
	num = int(inp[i:])
	while num > 2019:
		if num % 2019 == 0:
			s += 1
			num = num // 10
		elif num % 2019 < 10:
			num = num // 10
		elif num % 2019 < 100:
			num = num // 100
		elif num % 2019 < 1000:
			num = num // 1000
		else:
			num = num // 10000
print(s)

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = 0
if int(S) < 2019:
  print(ans)
else:
  for i in range(len(S)-3):
    for j in range(3, len(S)-i+1):
      T = S[i:i+j]
      N = int(T)
      if N % 2019 == 0:
        ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:

S = input()

Len = len(S)
N = 0
for Num1 in range(0, Len-2):
    #0-> 3
    #Len-4 -> Len-1
    Sum = int(S[Num1]) + int(S[Num1+1]) + int(S[Num1+2])
    for Num2 in range(Num1+4, Len+1):
        Sum += int(S[Num2-1])
        if(Sum%3 ==0):
            Num = int(S[Num1:Num2])
            if(Num%2019 ==0):
                N+= 1
print(N)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
s = int(S)
n = len(S)
count = 0
for i in range(1,n+1):
    for j in range(i+4,n+1):
        si = s%10**(n-i+1)
        sij = si//10**(n-j)
        if sij % 2019 == 0:
            count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
s=input()
cnt=0

for i in range(len(s)):
  for j in range(i+3,len(s)):
    if int(s[i:j+1])%2019==0:
      cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S=str(input())
count = 0
for i in range(len(S)-3):
  for k in range(i+3,len(S)):
#    print(S[i:k+1])
    if int(S[i:k+1]) % 2019 == 0:
      count = count + 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
len_s = len(s)
list_2019 = ['2019', '4038', '6057', '8076', '10095', '12114', '14133', '16152', '18171', '20190', '22209', '24228',
             '26247', '28266', '30285', '32304', '34323', '36342', '38361', '40380', '42399', '44418', '46437',
             '48456', '50475', '52494', '54513', '56532', '58551', '60570', '62589', '64608', '66627', '68646',
             '70665', '72684', '74703', '76722', '78741', '80760', '82779', '84798', '86817', '88836', '90855',
             '92874', '94893', '96912', '98931', '100950', '102969', '104988', '107007', '109026', '111045',
             '113064', '115083', '117102', '119121', '121140', '123159', '125178', '127197', '129216', '131235',
             '133254', '135273', '137292', '139311', '141330', '143349', '145368', '147387', '149406', '151425',
             '153444', '155463', '157482', '159501', '161520', '163539', '165558', '167577', '169596', '171615',
             '173634', '175653', '177672', '179691', '181710', '183729', '185748', '187767', '189786', '191805',
             '193824', '195843', '197862', '199881']
ans = 0
for i in range(4, len_s):
    for j in range(len_s):
        if (j + i <= len_s) and (''.join(s[j:j + i]) in list_2019):
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

S = input()
lenS = len(S)
S = int(S)
rui = []
for i in range(lenS + 1):
    rui.append((S % (10 ** i)) % 2019)

d = defaultdict(int)
for i in rui:
    d[i] += 1
ans = 0

for v, m in d.items():
    if m >= 2:
        ans += (m * (m - 1) // 2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
S = list(map(int,input().rstrip()))
l=len(S)
result=0
for i in range(0,int(l-3)):
    for j in range(i+4,int(l+1)):
        n = reduce( lambda a,b:10*a+b, S[i:j])
        if n %673==0 and n%3==0:
            result+=1
print(result)

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = tuple(input())
  count = 0
  for j in range(4,len(s)+1):
    for i in range(len(s) - j + 1):
      if int(''.join(s[i:i + j])) % 2019 == 0:
        count += 1
      if len(s) - j < 4:
        break

  print(count)




if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
n = input() #1行目のNを取得する
l = len(n)
count = 0
for i in range(l-3):
  for j in range(i+4,l+1):
      if int(n[i:j]) % 2019 == 0:
        count = count + 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
ans = 0
total_list = [0, int(S[0])]
for i in range(1, len(S)):
    total_list.append(total_list[-1]+int(S[i]))
for i in range(0, len(S)-3):
    for j in range(i+4, len(S)+1):
        if not((total_list[j]-total_list[i]) % 3):
            if not(int(S[i:j]) % 2019):
                ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
ans = 0

for i in range(len(s) - 3):
    for j in range(i + 4, len(s) + 1):
        tmp = int("".join(s[i:j]))
        if tmp % 2019 == 0:
            ans = ans + 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
ans = 0
for i in range(len(s)-1):
    for j in range(i+1,len(s)):
        num = int(s[i:j+1])
        if num % 2019 == 0:
            ans += 1
            i = j + 1
            #print(i,j)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=int(input())
S=[0] * (len(str(s))+1)
ans=0
for i in range(len(str(s))):
    S[-i-1]=int(str(s)[i:])
for i in range(len(str(s))+1):
    for j in range(i+5, len(str(s))+1):
        if (S[j]-S[i])%2019==0:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
#sys.exit()
#sorted( ,reverse=True)
S = str(input())
#S,T = map(int, input().split())
#A = list(map(int, input().split()))
#print(N)
#print(S,T)
#print(A)
ans = 0
for i in reversed(range(3,len(S))):
    for j in reversed(range(0,i-2)):
        #print(j,i+1)
        #print(S[j:i+1])
        
        if int(S[j:i+1]) % 2019 == 0:
            ans += 1
            break
        
        #print(S[j:i+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = len(s)
sum = 0
for i in range(l-4):
    if s[i] == '0':
        continue
    
    for j in range(i+4, l+1):
        if int(s[i:j]) % 2019 == 0:
            sum += 1

print(sum)

Submission status: Time Limit Exceeded

Solution code:

def main():
  s = input()
  ans= 0
  for i in range(len(s)):
    for j in range(i+4,len(s)):
      itoj = s[i:j+1]
      if (int(itoj) %  2019 ==0):
        ans+=1
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=[]
ans=0
for c in s:
    l=len(t)
    for i in range(l):
        t[i]*=10
        t[i]+=int(c)
        t[i]%=2019
        if t[i]==0:
            ans+=1
    t.append(int(c))
    t=list(set(t))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

count=0
for i in range(len(S)):
    for j in range(i+1, len(S)):
        if int(S[i:j+1]) % 2019 == 0:
            count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
wa = [0] * (n + 1)
wa[1] = int(s[0])
for i in range(n - 1):
    wa[i + 2] = wa[i + 1] + int(s[i + 1]) 
res = [0] * (n + 1)

i = n - 3
while i >= 0:
    m = 3
    while i + m < n:
        if (wa[i + m + 1] - wa[i]) % 3 == 0:
            if int(s[i:i+m+1]) % 673 == 0:
                res[i] = res[i] + res[i + m + 1] + 1
                break
        m = m + 1
    i = i - 1    

print(sum(res))

Submission status: Time Limit Exceeded

Solution code:
from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

T = S()

def match(v):
    return int(v) % 2019 == 0

cnt = 0

M = {}
for i in range(0, len(T)):
    for j in range(i+1, len(T)+1):
        s = T[i:j]
        if s in M:
            cnt += 1
            continue

        if match(s):
            M[s] = True
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
indexs = []
count = 0
for i in reversed(range(2,N)):
    check_num = int(S[i-2]+S[i-1]+S[i])
    if check_num % 19 == 0: # もしも19の倍数だったら
        indexs.append(i)
for i in indexs:
    for j in range(i):
        if int(S[j:i+1]) % 2019 == 0 :
            count = count + 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()

ans = 0

for i in range(len(S)):
  a = 0
  for j in range(i + 1, len(S) + 1):
    a = int(S[i:j])
    if a % 2019 == 0:
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def combinations_count(n):
  return n*(n-1)//2
s = input()
l = len(s)
lis = []
for i in reversed(range(l)):
  k = int(s[i:l])
  if i == l-1:
    lis.append(k%2019)
    tem = k
    tem2 = 1
    continue
  tem2 = (10*tem2)%2019
  kk = (int(s[i])*tem2+tem)%2019
  tem = k
  lis.append(kk)
lis.append(0)
lis.sort()
ll = len(lis)
ans = 0
tem = 1
for i in range(1, ll):
  if lis[i-1] == lis[i]:
    tem += 1
  elif tem >= 2:
    ans += combinations_count(tem)
    tem = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
S = input()
s = int(S)
res = 0
dics = [i for i in combinations(range(len(S)),2)]
for i in dics:
  a = s // (10**i[0])
  b = s // (10**(i[1]+1))
  c = a - b*(10**(i[1]+1-i[0]))
  if c %2019 ==0:
    res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
S = input()
# print(S)

if int(S) < 2019:
    print(0)
    exit()

count = 0
for i in range(0, (len(S) - 3)):
    found = False
    for j in range(i + 3, len(S)):
        number = int(S[i:j + 1])
        if number % 2019 == 0:
            # print(number, i, j)
            count += 1
            found = True
            break
    
    if found:
        i = j

print(count)

# for i in range(1, 101):
#     print(i, 2019 * i)

# 242281
# 2422
# 24228
#  4222
#  42221

# 12114
# 121140

Submission status: Time Limit Exceeded

Solution code:
S = input()
R = 0
for i in range(0,len(S)):
    for j in range(1,len(S) + 1):
        if S[i:j] != "":
            N = int(S[i:j])
            if N % 2019 == 0:
                R += 1
print(R)

Submission status: Time Limit Exceeded

Solution code:
S=input()
count=0
for i in range(0,len(S)-4):
    for j in range(i+3,len(S)):
        if int(S[i:j+1])%2019==0:
            count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
s=input()
N=len(s)
ans=0
li=[1,2,4,6,8]
num=[]

for i in range(N):
    if int(s[i]) in li:
        num.append(i)

for i in num:
    for j in range(i+4,N):
        if int(s[i:j+1])%2019==0:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
s_len=len(s)+1

l=list()
ans = 0
for i in range(0,s_len):
    for j in range(i+1,s_len):
        if int(s[i:j]) % 2019 == 0:
            ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
if n<10000:
  if n%2019 == 0:
    print(1)
  else:
    print(0)
else:
  x=str(n)
  c=0
  for i in range(len(x)-4):
    for j in range(i+4, len(x), 4):
      f = int(x[i:j+1]) 
      if f<10000:
        if f%2019 == 0:
          c+=1
      elif f % 2019 == 0:
        c+=1
  print(c)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
c = 0
for x in range(len(S)):
  for y in range(len(S)):
    if (len(S[x:y+1]) == 0):
      continue
    if int(''.join(S[x:y+1])) % 2019 == 0:
      c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
s = input()
ans = 0
for i in range(len(s)):
    a = int(s[i:])
    while a > 1000:
        if a % 2019 == 0:
            ans += 1
        a //= 10
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
cnt = len([int(s[j:j+i]) for i in range(5, len(s)+1) for j in range(len(s) - (i - 1)) if int(s[j:j+i]) % 2019 == 0])
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s=input()
lst=[]
count=0
for i in range(4,len(s)+1):
    for j in range(0,len(s)-i+1):
    
        if int(s[j:j+i])%2019==0:
            count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations as C

S = input()
S_l = len(S)

count = 0
k = [i for i in list(C(list(range(S_l)), 2)) if i[1] - i[0] > 2]

for i in k:
    n = int(S[i[0] : i[1] + 1])
    if n % 2019 == 0:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())

counter = 0
for start in range(len(S)):
    for end in range(start+3,len(S)+1):
        if int(S[start:end]) % 2019 == 0:
            counter += 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
S = input()
count = 0
for i in range(len(S)):
    for j in range(i,len(S)):
        if j-i+1 > 3:    
            a = S[i:j+1]
            a = int(a)
            if a%2019 == 0:
                count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N=input()
# N='1817181712114'
count=0
for i in range(len(N)-3):
    for j in range(i+4,len(N)+1):
        
#         print(N[i:j])
        if int(N[i:j])%2019==0:
            count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S=list(map(str,input()))
#print(S)
p=0;K="0"
for i in range((len(S)-3)):
  for j in range(i+3,len(S)+1):
    for k in S[i:j]:
      K=K+k
    if int(K)!=0 and int(K)%2019==0:
      p=p+1
    K="0"
print(p)

Submission status: Time Limit Exceeded

Solution code:
S = input()
len = len(S)
List =[]
for i in range(0,len-3):
  for j in range(i+4,len+1):
    num = int(S[i:j])
    List.append(num%2019)
      

print(List.count(0))

Submission status: Time Limit Exceeded

Solution code:
# Problem D
s = input()
count_ij = 0
for i in range(len(s) - 4):
    for j in range(i + 5, len(s)+1):
        sub_s = int(s[i: j])
        if sub_s % 2019 == 0:
            count_ij += 1

print(count_ij)

Submission status: Time Limit Exceeded

Solution code:
x = input()
i = 0
res = 0
while len(str(i)) < len(x):
    i += 2019
    res += x.count(str(i))
print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 20:57:47 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

x = 2019
S = input()
l = len(S)

a, b = [],[0]
s = ''
for i in range(l):
#    a.append(int(S[:i+1]) % x)
#    if S[i] != '0':
    s = S[-i-1] + s
    b.append(int(s) % x)

ans = 0

xx = [0 for _ in range(2019)]
for i in range(len(b)):
    xx[b[i]] += 1

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)

Submission status: Time Limit Exceeded

Solution code:
s=input()
slen=len(s)
count=0
skip=0
for i in range(slen-4):
  for j in range(i+4,slen):
    if skip != 0:
      skip+=1
      skip%=5
      continue
    targ=int(s[i:j+1])
    if targ%2019==0:
      count+=1
      skip+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
S = input()
n = len(S)

L = [(10**(n - i - 1) * int(s)) % 2019  for  i, s in enumerate(S)]

count = 0
for i in range(n):
    count += (np.cumsum(L[i:]) % 2019 == 0).sum()

print(count)

Submission status: Time Limit Exceeded

Solution code:
#A,B,C,D=map(int,input().split(" "))

mod=2019
a=input()

N=len(a)
t=[]
ans=0

for i in range(N):
  for j in range(i+1,N+1):
    u=int(a[i:j])
    #print(u)
    if (u % mod)==0:
      ans+=1
      #print(i+1,j)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
N=[0]*2020
for i in reversed(range(n)):
    N[int(s[i:])%2019]+=1
ans=s.count('0')
ans+=N[0]
for j in N:

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
s = input()
n = len(s)
b = Counter()
cnt = 0
for l in range(n-3):
    r = l+3
    while int(s[l:r+1])%2019 != 0 and r < n:
        r += 1
    if int(s[l:r+1])%2019 == 0:
        cnt += 1+b[l]
        b[l] += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = input()

match = 0
end = len(s)
for i in range(end - 3):
    for j in range(i + 5, end + 1):
        # print(int(s[i:j]))
        if int(s[i:j]) % 2019 == 0:
            match += 1

print(match)

Submission status: Time Limit Exceeded

Solution code:
s = input()
s_l = len(s)
r = 0
n = 1
while n <= 200000:
    a = 2019 * n
    if int(s) < a:
        break
    a_l = len(str(a))
    a_s = str(a)
    flag = False
    for i in a_s:
       flag = not i in s
    if flag:
        n += 1
        continue
    
    for i in range(1,s_l + 1):
        if i + a_l - 1 > s_l:
            break
        elif s[i - 1:i + a_l - 1] == a_s:
            r += 1
    n += 1
print(r)

Submission status: Time Limit Exceeded

Solution code:
s=input()
counter=0
if len(s)<=3:
  print(0)
else:
  for i in range(len(s)+1):
    for j in range(i+4,len(s)+1):
        test_case=int(s[i:j])
        if test_case%2019==0:
    	    counter += 1
  print(counter)

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = 0
for i in range(len(S)):
  for j in range(i,len(S)):
    if int(S[i:j+1])%2019 == 0: ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

j_max = len(S)

count = 0

for i in range(j_max-3):
    for j in range(i+3, j_max):
        target = int(S[i:j + 1])
        if (target % 2019 == 0):
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
s = str(input())

count = 0
for i in range(len(s)):
  for j in range(len(s)-i-3):
    if int(s[i:i+4+j]) % 2019 == 0:
      count += 1
      
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
count = 0

a = []
i = 0
while True:
    i += 2019
    if i >= 200000:
        break
    a.append(str(i))

for i in range(len(S) + 1):
    for j in range(len(S) -i +1):
        s = S[i:i + j]
        count += a.count(s)

# a = []
# i = 0
# while True:
#     i += 2019
#     if i >= 200000:
#         break
#     a.append(str(i))
#
# for i in range(len(a)):
#     s_count = S.count(a[i])
#     if s_count != 0:
#         print(a[i])
#     count += s_count
#
# print(a)
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
cnt = 0
is_end = [False] * (len(S) + 1)
for i in range(len(S)):
    if is_end[i]:
        continue
    is_end[i] = True
    bingo = [i]
    r = 0
    for j in range(i+1, len(S)+1):
        r = r * 10 + int(S[j-1])
        if is_end[j]:
            continue
        r %= 2019
        if r == 0:
            is_end[j] = True
            bingo.append(j)
    l = len(bingo)
    if l >= 2:
        cnt += int(l*(l-1)/2)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = input()

ans = 0
for i in range(4,len(s)):
	j = 0
	while j+i <= len(s):
		temp = int(s[j:j+i])
		if temp%2019!=0:
			j+=1 
			continue
		else: 
			j+=1
			ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = len(s)
lst = [None for i in range(l)]
lst[0] = int(s[0])
for i in range(l-1):
    lst[i+1] = lst[i]+int(s[i+1])
lst = [0]+lst
# print(lst)

ans = 0
for i in range(l):
    for j in range(i,l):
        if (lst[j+1]-lst[i])%3==0:
            if int(s[i:j+1])%673==0:
                ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
ans = 0
idx_i = 0
while idx_i < len(s) - 4:
    for i in range(idx_i, len(s)-4):
        for j in range(i+4, len(s)):
            if int(s[i:j+1]) % 2019 == 0:
                ans += 1
                idx_i = j
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import os

import math
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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


# MOD = 998244353
def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def get_factors(n):
    """
    素因数分解
    :param int n:
    :rtype: list of int
    """
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


S = sys.stdin.buffer.readline().decode().rstrip()
N = len(S)
MOD = 2019

hist = []
mod_counts = [0] * MOD
power = 1
n = 0
for i in reversed(range(N)):
    n += int(S[i]) * power
    n %= MOD
    mod_counts[n] += 1
    hist.append(n)
    power *= 10
    power %= MOD

ans = 0
m = 0
power = 1
for i in reversed(range(N)):
    # m = int(S[i + 1:] or 0) % MOD
    ans += mod_counts[m]
    mod_counts[hist[::-1][i]] -= 1

    m += int(S[i]) * power
    m %= MOD
    power *= 10
    power %= MOD
print(ans)



def test(S, mod):
    ans = 0
    for l in range(len(S)):
        for r in range(l + 1, len(S) + 1):
            n = int(S[l:r])
            if n % mod == 0:
                print(n)
                ans += 1
    print(ans)


# test(S, 2019)
# print()
# test(S, 2019 // 3)

Submission status: Time Limit Exceeded

Solution code:
N = input()
lenN = len(N)
cnt = 0
  
for i in range(0,lenN-3):
  for j in range(i + 3,lenN + 1):
    if j - i > 200000:
      break
    p = int(N[i:j])
    if p % 2019 == 0:
      cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S = input()
n = 0
for i in range(len(S)-3):
    if int(S[i]) == (1 or 0) and (i != len(S)-3):
        for j in range(i+4,len(S)):
            if(int(S[i:j+1])%2019 == 0):
                n = n+1
    elif int(S[i]) != (1 or 0):
        for j in range(i+3, len(S)):
            if(int(S[i:j+1])%2019 == 0):
                n = n+1
print(n)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
count = 0

for i in range(n-3):
    for j in range(i+3, n):
        if int(s[i:j+1]) % 2019 == 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
s=input()
ans=0

for j in range(len(s)-4):
  test=(1000*int(s[j])+100*int(s[j+1])+10*int(s[j+2])+int(s[j+3]))%2019

  for i in range(j+4,len(s)):
    test=(test*10+int(s[i]))%2019
    if test==0:
      ans+=1
  
print(str(ans))

Submission status: Time Limit Exceeded

Solution code:
S = abs(int(input()))
# S = abs(int(1817181712114))
strS = str(S)
length = len(strS)

multiple = 0

for i in range(0, length-3) :
    for j in range(i+4, length+1) :
        num = strS[i:j:1]
        intNum = int(num)
        if intNum <= 200000 :
            if intNum % 2019 == 0 :
                multiple += 1

print(multiple)

Submission status: Time Limit Exceeded

Solution code:
s = input()
a = [int(c) for c in s]

b=""
count=0

for i in range(len(a)):
    for j in range(i,len(a)):
        for k in range(i,j+1):
            b += str(a[k])
        #print(b)
        if int(b)%2019 == 0:
            count+=1
        b=""

print(count)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
result = 0
for i in range(5, n):
    for j in range(n - i + 1):
        sub_s = s[j:j+i]
        if int(sub_s) % 2019 == 0:
            result += 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
import re
S=input()

x=[i for i in range(1,200000)]
x=map(lambda i:str(i*2019),x)



ans=0

for i in x:
    t=len(re.findall("(?={})".format(i),S))
    ans+=t

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
count = 0
num = []

for i in range(len(s)):
    for j in range(len(s)-i):
        num = []
        for k in range(j+1):
            num += s[i+k]
        num = ''.join(num)
        if int(num)%2019 == 0:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
s = int(input())

n = len(str(s))

k = 0

for i in range(n - 4):
    for j in range(i+4, n+1):
        if int(str(s)[i:j]) % 2019 == 0:
            k = k+1
            
print(k)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
cnt=0

for i in range(len(s)):
  for j in range(i+4,len(s)+1):
    if int(s[i:j])%2019==0:
      cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s=str(input())

ans=0
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        if int(s[i:j])%2019==0:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
count = 0

for i in range(len(S)-3):
    for j in range(i+3, len(S)+1):
        s = int(S[i:j])
        if s%2019 == 0:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
ans = 0
for i in range(n-4):
    for j in range(i+1, n+1):
        num = int(s[i:j])
        if num % 2019 == 0:
            ans += 1
            i = j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
S = input()
cum = []
heapq.heapify(cum)
for i in range(len(S)-1, -1, -1):
    n = int(S)
    n = n % 10**(i+1)
    heapq.heappush(cum, n % 2019)

prev = cum[0]
ans = 0
cnt = 0
for i in range(len(cum)):
    c = heapq.heappop(cum)
    if c != prev:
        if prev == 0:
            ans += cnt
        ans += cnt * (cnt-1) // 2
        cnt = 1
    else:
        cnt += 1
    prev = c

if cnt > 1:
    if prev == 0:
        ans += cnt
    ans += cnt * (cnt-1) // 2
    cnt = 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = int(input())
len = len(str(s))
s_list = list(str(s))
ans = 0
for i in range(len - 3):
    for j in range(i + 3, len):
        num_wk = s_list[i:j+1]
        num = ''.join(num_wk)
        if int(num) % 2019 == 0:
                ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input() #sys.stdin.readlineは最後が改行
n =len(s)

from collections import defaultdict
amari = defaultdict(lambda:0)
amari[0]=1
num=0
tmp=0

for i in range(n):
    num = tmp + int(s[-1-i])*(10**(i))
    tmp = num%2019
    amari[tmp]+=1

from math import factorial

ans = 0
for key,val in amari.items():
    if val>1:
        ans +=factorial(val) // factorial(2) // factorial(val - 2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
a=input()
ct=0
mylist=list(range(len(a)+1))
for i in itertools.combinations((mylist),2):
    b,c=i
    if abs(b-c)<4:
        pass
    elif int(a[b:c])%2019==0:
        ct+=1
print(ct)

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = list(input())
    N = len(S)
    ans = 0
    m = 2019
    div_list = [0]*m
    div_list[0] += 1
    num = 0
    for i in range(N):
        num += 10**i*int(S[N-i-1])
        div_list[num%m] += 1

    for item in div_list:
        if item >= 2:
            ans += int(item*(item-1)/2)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
str1=input("")
count=0;
test = "2019"

while(len(str1)>=len(test)):

  if test in str1:
    count+=1
  test = str(eval(test)+2019)
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = int(input())
k = len(str(S))
a = []
for j in range(4,k+1):
  for i in range(1,j-2):
    l = S % 10**(k-i+1)
    m = l // 10**(k-j)
    if m % 2019 == 0:
      a.append(i)
      
print(len(a))

Submission status: Time Limit Exceeded

Solution code:
s = input()
cnt = 0
for l in range(len(s)):
    for r in range(1, len(s)):
        if l + r > len(s):
            break
        # print(s[l:l + r])
        if int(s[l:l + r]) % 2019 == 0:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
import numpy as np
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
MOD = 10**9+7
import itertools
import math
import functools

s = input()
li = [0]
c = 2019
for i in range(1,110):
    li.append(c*i)
cnt = 0
for i in range(len(li)):
    a = str(li[i])
    for j in range(len(s)-len(a)+1):
        c = ""
        for k in range(len(a)):
            c += s[j+k]
        if c == a:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S = input()
Ns = len(S)
Nres = 0
for i in range(Ns-3):
    for j in range(i+4,Ns+1):
        # print(i,j)
        if int(S[i:j])%2019==0:
            # print(i,j)
            Nres +=1
        # print(int(S[i:j]))
print(Nres)

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = 0
# print(len(S))

if int(S) < 2019:
     ans = 0
else:
     # for i in range(int(int(S)/2019)):
     #      ans += S.count(str(2019*(i+1)))
     for i in range(len(S)-3):
          for j in range(len(S)-3-i):
               if int(S[j:j+4+i])%2019==0:
                    ans+=1
               # print(S[j:j+4+i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
val = [int(s[0])]
z = [-1]
o = []
t = []
if val[0]%3 == 1:
	o.append(0)
elif val[0]%2 == 1:
	t.append(0)

for i in range(1, n):
	val += [(val[-1] + int(s[i]))%3]
	if val[-1] == 0:
		z.append(i)
	elif val[-1] == 1:
		o.append(i)
	else:
		t.append(i)
		
count = 0
for i in range(len(z)):
	for j in range(i + 1, len(z)):
		if int(s[z[i]+1:z[j]+1]) % 673 == 0:
			count+=1
for i in range(len(o)):
	for j in range(i + 1, len(o)):
		if int(s[o[i]+1:o[j]+1]) % 673 == 0:
			count+=1
for i in range(len(t)):
	for j in range(i + 1, len(t)):
		if int(s[t[i]+1:t[j]+1]) % 673 == 0:
			count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections
s = input()
lst = []
for i in range(len(s)):
  n = int(s[i::])
  lst.append(n%2019)
lst.append(0)

ans = 0
for i in range(2018):
  m = lst.count(i)
  ans += m*(m-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=str(input())
count=0

for i in range(len(S)):
    for j in range(i+1,len(S)+1):
        sum=int(S[i:j])%2019
        if sum==0:
            count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def count2019(str, l, k): 
    count = 0
    for i in range(l): 
        n = 0
        for j in range(i, l, 1): 
            n = n * 10 + (ord(str[j]) - ord('0')) 
            if (n % k == 0): 
                count += 1
    return count 
def main():
    s=input()
    print(count2019(s,len(s),2019))


if __name__=='__main__':
    main()