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:
def digitSum(n):
    # １文字ずつ数値化し配列にする。
    array = list(map(int, n))
    # 合計値を返す
    return sum(array)

S = input()
ans = 0
# print(len(S))
lS = 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(lS-3):
          for j in range(lS-3-i):
               obj = S[j:j+4+i]
               if digitSum(obj)%3 == 0:
                    if int(obj)%2019==0:
                         ans+=1
               # print(S[j:j+4+i])

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
count_start = 0
count_end = 1
kumi = []
while count_start <= len(S) - 1:
    count_end = 1
    while count_end <= len(S):
        if count_start < count_end:
            kensa = int(S[count_start:count_end])
            if kensa % 2019 == 0:
                kumi.append(kensa)
        count_end += 1
    count_start += 1
print(len(kumi))

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
s = int(S)
count = 0
for j in range(1,N+1):
    for i in range(1,j+1):
        if i==1:
            t=0
        else:
            t = (s//(10**(N-i+1)))*(10**(N-i+1))
        t = s-t
        t = t//(10**(N-j))
        if t % 2019 == 0 and t != 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
s = input();
#s = "14282668646"
ans = 0;

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(20000*20000)

S = str(input())
ans = set()

def dfs(i, j):
    if int(S[i:j+1])%2019 == 0:
        ans.add((i, j))
    if j == len(S)-1:
        return

    dfs(i, j+1)
    dfs(i+1, j+1)

if len(S) < 4:
    print(0)

else:
    dfs(0, 3)
    print(len(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):
    if len > 4:
        for j in range(i + 4, 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()
n=len(s)
N=[0]*2020
x=0
for i in reversed(range(n)):
    x+=int(s[i])*(10**(n-i-1))
    x%=2019
    N[x]+=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:
s = input()
n = len(s)
a = 0
for i in range(n-4):
  for j in range(i+5,n+1):
    x = s[i:j]
    y = int(x)
    if y % 2019 == 0:
       a += 1
print(a)

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
s = input()
count = 0
for i in range(len(s)):
    for j in range(i+5, len(s)+1):
        if (int(s[i:j]) % 2019 == 0):
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


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


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


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
s = input()
cnt = 0
tmp = []
tmp2 = []
for i in range(len(s)+1):
    for j in range(len(s)+1):
        # print(s[i:j])
        if s[i:j] != '':
            if int(s[i:j]) % 2019 == 0:
                cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S = input()

N = int(S) // 2019

count = 0

for i in range(1, N + 1):
  count += S.count(str(2019 * i))

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
# input処理を高速化する
input = sys.stdin.readline

S=input()
N=len(S)

number=''
cnt=0


for i in range(N-2):
    for j in range(i+4,N):
        number=S[i:j]
        if int(number)%2019 ==0:
            cnt+=1
            continue

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# l=[]
# z=2000000
# cnt=1
# while 2019*cnt <=z:
#     l.append(2019*cnt)
#     cnt +=1

# for i in l:
#     print(i)


s=input()
ss=len(s)
res=0
target=2019

l=r=0
ff=False

for i in range(ss-4):
    l=i
    ff=False
    for j in range(i+4,ss+1):
        r=j

        tmp=int(s[l:r])
        # print(tmp)
        if ff == True and s[r] != '0':break


        if tmp % target ==0:
            # print('xxxx',tmp)
            ff=True
            res+=1

print(res)

Submission status: Time Limit Exceeded

Solution code:
S=input()
ans = 0
for i in range(len(S)-4):
    k=5
    while k-(len(S)-i) < 1:
        if int(S[i:i+k]) % 2019 != 0:
            k+=1
        else:
            ans +=1
            k+= len(S[i:i+k])-3
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
k=0
sij0=0
sij1=0
l=len(s)
for i in range(l-3):
  sij0=int(s[i:i+4])
  #print(sij0)
  sij0=sij0 % 2019
  if sij0 == 0:
    k=k+1
  for j in range(i+4,l):
    sij1=int(s[j])
    sij0*=10
    sij0+=sij1
    sij0 = sij0 % 2019
    if sij0 == 0:
      k=k+1
print(k)

Submission status: Time Limit Exceeded

Solution code:
a=input()
l=len(a)
c=0
l1=l+1
l3=l-3
for x in range(l3):
  x4=x+4
  for y in range(x4,l1):
    n=int(a[x:y])
    if n%2019==0:
      c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:

S = str(input())

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()

def check_2019(txt):
  amari = int(txt) % 2019
  if amari == 0:
    return True
  else:
    return False

N = len(S)

ans = 0

for i in range(0, N-2):
  for j in range(i+4, N+1):
    # print(S[i:j])
    if check_2019(S[i:j]):
      ans += 1
      i = j
      break
    else:
      pass

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

S=int(input())
n=int(math.log10(S))+1
cnt=0

for i in range(4,n+1):
  for j in range(n-i+1):
    a=(S//(10**(n-i-j))%(10**(i)))
    if a%2019==0:
      cnt+=1
      
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
inp=input()
inp_list=list(inp)
cnt=0
#print(inp_list)
for i in range(len(inp_list)):
    for j in range(int(len(inp_list)- i)):
        a=0
        a="".join(inp_list[i:i+j+1])
        if int(a) > 0:
            answer=int(a)%2019
            if answer==0:
                cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

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

count=0

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
#d
N = int(input())
s  = str(N)
a =[]

def func(string,p):
    count=0
    for x in range(len(string)-len(p)+1):
        if string[x:x+len(p)]==p:
            count+=1
    return count

def fun(a,b):
    ans=0
    for x in range(len(a)-b+1):
        if int(a[x:x+b])%2019==0:
            ans+=1
    return ans

for i in range(1,496):
    a.append(str(2019*i))
if len(s)<4:
    print(0)
else:
    ans=0
    for x in range(3,len(s)):
        ans+=fun(s,x)
    print(ans)

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
Scount = 0
Slen = len(S)
for i in range(Slen-1):
    for j in range(1,Slen):
        if (i+j)<=Slen:
            part_S = S[i:i+j]
            num = int(part_S)
            if num % 673 == 0:
                num = num//673
                if num % 3 ==0:
                    Scount += 1
print(Scount)

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = 0
for i1 in range(len(S)):
    for i2 in range(i1+1,len(S)+1):
        num = int(S[i1:i2])
        if num%2019 == 0:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
n = len(s)

dp = [[0]*2019 for _ in range(n+1)]

if n<4:
    print(0)
    exit()

dp[1][int(s[0])] = 1

for i in range(1,n):
    keta = int(s[i])
    dp[i+1][keta] += 1
    for j in range(2019):
        dp[i+1][(j*10+keta) % 2019] += dp[i][j]

ans = 0
for i in range(1,n+1):
    ans += dp[i][0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
ans = 0
a = set(2019*i for i in range(1, 99))
        
for i in range(len(s)):
    for j in range(i+4, len(s)+1):
        if int(s[i:j]) in a:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=input()
cnt=0

for n in range (4,len(S)+1):
    for m in range(len(S)+1-n):
        if int(S[m:m+n])%2019==0:
            cnt+=1
        else:
            continue

print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
if len(s) <= 3:
  print(0)
  exit()

chk = [str((i+1)*2019) for i in range(1000)]
ans = 0
for i in chk:
  for j in range(len(s)-len(i)+1):
    ans += s.count(i,j,j+len(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#0がない
s = input()
ans = 0
size = len(s)
for i in range(size):
    for j in range(i+5, min(size+1, i+200)):
        if int(s[i:j])%2019==0:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = str(input())
num = int(n)
count = 0
roop = 0
while (2019 * roop) < num:
    roop += 1
    count += n.count(str(2019*roop))
print(count)

Submission status: Time Limit Exceeded

Solution code:
s = input()

n = len(s)

k = 0

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

S = input()
N = len(S)
"""
L4 = []
L5 = []
L6 = []
L7 = []
L8 = []
for i in range(10000):
    t = len(str(i*2019))
    if t == 4:
        L4.append(i*2019)
    if t == 5:
        L5.append(i*2019)
    if t == 6:
        L6.append(i*2019)
    if t == 7:
        L7.append(i*2019)
    if t == 8:
        L8.append(i*2019)
#print(len(L4),len(L5),len(L6),len(L7))

"""
counter = 0

for i in range(N-3):
    #j = 4
    #while (j < N+1-i):
    M = min(9,N+1-i)
    for j in range(4,M):
        if int(S[i:i+j]) % 2019 == 0:
            counter += 1
            for k in range(j+1,N+1-i):
                if int(S[i:i+k]) % 2019 == 0:
                    counter += 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
#この解放だとTLE....
s = input()
c = 0
l = len(s)
for i in range(l+1):   #開始インデックスを外側のループに
  for j in range(i+1, l+1):  
        #print(s[i:j])
        if(int(s[i:j]) % 2019 == 0):
            c += 1        
print(c)

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)]
ress = [s//(10**i[0])- (s // (10**(i[1]+1)))*(10**(i[1]+1-i[0])) for i in dics]
print(sum(x %2019 == 0 for x in ress))

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
n = len(S)
Ss = [int(S[i:j+1])%2019 == 0 for i in range(0,n-3) for j in range(i+3,n)]
print(sum(Ss))

Submission status: Time Limit Exceeded

Solution code:
S = input()
count = 0
for i in range(len(S)):
    if i+4 == len(S):
        j = i + 4
        number = int(S[i:j])
        if number == 2019:
            count += 1
        break
    try:
        for n in range(4,len(S)+1):
            j = i + n
            number = int(S[i:j])
            if number % 2019 == 0:
                if j == len(S)+1:
                    break
                else:
                    count += 1
            else:
                pass
    except IndexError:
        break
print(count)

Submission status: Time Limit Exceeded

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

for i in range(n):
    a = int(s[i])
    for j in range(i+1,n):
        a += int(s[j])
        if a % 3 == 0:
            if int(s[i:j+1]) % 673 == 0:
                   ans += 1
                   
print(ans)

Submission status: Time Limit Exceeded

Solution code:

s=input()

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math


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


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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s=str(input())
n=len(s)
k=[0]*(n+1)
for i in range (1,n+1):
    k[i]=int(s[i-1])
t=[0]*(n+1)
t[0]=0  
for i in range(1,n+1):
    t[i]=(10*t[i-1]+k[i])%2019

p=1
q=[0]*448
for z in range(0,448):
    q[z]=p%2019
    p=10*q[z]

d=0    
for j in range(n+1):
    for l in range (j):
        f=(j-l)%448
        if (t[l]*q[f]-t[j])%2019==0:
            d+=1
            
print(d)

Submission status: Time Limit Exceeded

Solution code:
# if the remainders (mod 2019) are equal, the difference will be divisible
# x = Q*2019+5 y = R*2019+5 then x-y=(Q-R)*2019
# unless Q-R<=0
# where the substring itself is (Q-R)*2019/10**(something)
# 2019 = 3*673 in prime factorization
# so multiplying by 10 doesn't affect whether a number is divisible by it
from collections import Counter
s = input()
remainders = [int(s[i::])%2019 for i in range(len(s))]
histo = Counter(remainders)
non_single_count = int(sum(count*(count-1)/2 for value, count in histo.items() if value!=0))
single_count = int(sum(count for value, count in histo.items() if value==0))
print(non_single_count+single_count)

Submission status: Time Limit Exceeded

Solution code:
import collections
from sys import stdin


def get_result(data):
    S = data[0]
    int_S = int(S)
    mod_all_bit = [0]
    for i in range(len(S)):
        mod_all_bit.append(int_S % (10**(i+1)) % 2019)
    c = collections.Counter(mod_all_bit)
    ans = 0
    for key, val in c.items():
        if val >= 2:
            ans += int(val * (val-1) * 0.5)
    return ans


if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)

Submission status: Time Limit Exceeded

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

s = ns()
b = [0]
for i in range(len(s)):
    b.append(int(s[i:])%2019)

import collections

c = collections.Counter(b)
ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()

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

    n = 0
    count = 0

    for i in range(len(s)-3):
        for j in range(i+3, len(s)):
            n = s[i:j+1]

            # print(n)
            if int(n) % 2019 == 0:
                count += 1

    print(count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
aaa = input()

b = 0
ans = []

a = 0
c = 4
for a in range(0,len(aaa)-4):
    for c in range(a + 4,len(aaa)+1):
        b = aaa[a:c]
        if int(b) % 2019 == 0:
            ans.append(b)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
N=[0]*2020
x=0
for i in reversed(range(n)):
    x+=int(s[i])*(10**(n-i-1))
    N[x%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:
#coding:utf-8

s = str(input())
n = len(s)
count = 0
s = int(s)

for i in range(n):
    num = s % (10 ** (n - i))
    for j in range(1,n+1):
        if num == 0:
            break
        elif num % 2019 == 0:
            count += 1
            break
        num = num // 10

print("{}".format(count))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):  # can't use a to specify default for hi
    hi = hi if hi is not None else len(a)  # hi defaults to len(a)   
    pos = bisect_left(a, x, lo, hi)  # find insertion position
    return pos if pos != hi and a[pos] == x else -1  # don't walk off the end 
def solve(a):
    n=len(a)
    k=673
    k2=3
    numMultiples = 0
    #seenRemainders = [[] for i in range(n)]
    seenRemainders = defaultdict(list)
    seenRemainders2 = defaultdict(list)
    for i in range(0,n):
        remainder = 0
        remainder2=0
        prefixesFound = 0
        for j in range(i,n):
            remainder = (10 * remainder + int(a[j])) % k
            remainder2 = (10 * remainder2 + int(a[j])) % k2
            # if remainder in seenRemainders[j] and remainder2 in seenRemainders2[j]:
            #     break
            # seenRemainders[j].sort()
            # seenRemainders2[j].sort()
            if binary_search(seenRemainders[j],remainder)!=-1 and binary_search(seenRemainders2[j],remainder2)!=-1:
                break
            seenRemainders[j].append(remainder)
            seenRemainders2[j].append(remainder2)
            #add remainder to seenRemainders[j]
            if remainder == 0 and remainder2==0 :
                prefixesFound+=1
        numMultiples += prefixesFound * (prefixesFound + 1) / 2
    return numMultiples
s=input()
print(int(solve(s)))

Submission status: Time Limit Exceeded

Solution code:
s = input()

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

print(cnt)

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



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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
cnt = 0
for i in range(N-4):
    if int(S[i]) % 2 == 1 and int(S[i]) != 1:
        pass
    else:
        for j in range(i+3,N):
            if int(S[i:j+1]) % 2019 == 0:
                cnt += 1
            else:
                pass
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = input()

ans = 0
n = len(s)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
S=list(input())
SS=""
N=len(S)

MAX=2100
MOD=10**9+7

fac=[None for i in range(MAX)]
finv=[None for i in range(MAX)]
inv=[None for i in range(MAX)]

def COMinit(num):
    global fac
    global finv
    global inv
    fac[0]=1
    fac[1]=1
    finv[0]=1
    finv[1]=1
    inv[1]=1

    for i in range(2,num):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD

def COM(n,k):
    if n<k:
        return 0
    elif n<0 or k<0:
        return 0
    else:
        return int(fac[n] * (finv[k] * finv[n - k] % MOD) % MOD)


COMinit(MAX)

M=[[0 for j in range(10)] for i in range(2019)]

ans=0

for i in range(N):
    SS="".join([S[-(1+i)],SS])
    num=int(SS)
    I=num%2019
    if I==0:
        ans+=1
    syou=num//2019
    J=syou%10
    M[I][J]+=1

for i in range(2019):
    for j in range(10):
        if M[i][j]>=2:
            ans+=COM(M[i][j],2)

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
h = [int(x) for x in list(S)]
N = len(h)
c = 0
for i in range(0, N+1):
    for j in range(i, N+1):
        b = 0
        for k in range(i, j):
            b = b * 10 + h[k]
        if b != 0 and b % 2019 == 0:
            c += 1
print(c)

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+5,len(s)+1):
    if int(s[i:j])%2019==0:
      cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
    
def print_ans(S):
    """Test Case
    >>> print_ans('1817181712114')
    3
    >>> print_ans('14282668646')
    2
    >>> print_ans('2119')
    0
    """
    target_list = []
    itr = 2019
    for i in range(1, 9906):
        tmp = i * itr
        if tmp > int(S):
            break
        elif '0' in list([s for s in str(tmp)]):
            continue
        else:
            target_list.append(tmp)
    ans = 0
    if len(S) <= 3:
        print(0)
    else:
        for i in range(len(S)-2):
            for j in range(i + 2, len(S)):
                tmp = S[i:j+1]
                if int(tmp) in target_list:
                    ans = ans + 1
        print(ans)
            
            

if __name__ == '__main__':
    S = input().rstrip()
    print_ans(S)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)
mod = 1000000007


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


# Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
a=str(input())
ans=0
b=[]
for i in range(len(a)-3):
  for j in range(i+3,len(a)+1):
    b=int(a[i:j])
    if b<2019:
      continue
    if b%2019==0:
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())

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


print(counter)

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
nums = []
const = 2019
times = 1
while const <= 200000:
    times += 1
    nums.append(str(const))
    const += 2019


def check(s, nums):
    s_list = list(map(str, s))
    cnt = 0
    for i in range(len(s)):
        for j in range(len(s) - (i + 1)):
            if j + i >= 3:
                if "".join(s_list[i:i + j + 2]) in nums:
                    cnt += 1
    return cnt


print(check(s, nums))

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/abc164/tasks/abc164_d

s=input()
count=0
for i in range(len(s)):
    for j in range(i+4,len(s)+1):
        str_num=s[i:j]
        #print(str_num)
        num=int(str_num)
        if num%2019==0:
            count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())

lenS = len(S)

sweep = 4
flag = 0
ans = 0
mem = 0
step = 1

if lenS < 3:
    print(0)
else:
    while sweep <= len(S):
        step = 1
        for i in range(mem, lenS - sweep + 1, step):
            if int(''.join(S[i:i + sweep])) % 2019 == 0:
                ans += 1
                step = sweep-1

        sweep += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())

count = 0

for i in range (len(S)-4):
    #N桁で区切る
    for n in range (4, len(S)+1-i):
        j = i + n
        num = int(S[i:j])
        if(num % 2019 == 0):
            #print(num)
            count = count + 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
l = []
for i in range(1, 10000000):
    l.append(str(2019*i))

s = input()
ans = dict()
for i in l:
    if i in s:
        for j in range(len(s)-len(i)+1):
            if s[j:j+len(i)] == i:
                ans[str(j+1)+"-"+str(j+len(i))] = 1

# print(l)
print(len(ans))
# print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
c=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:
            c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
S=input()
c=0
for i in range(len(S)-4):
    j=i+4
    while(j<len(S)):
        if(int(S[i:j+1])%2019==0):
            c+=1
            j+=5
        else:
            j+=1
print(c)

Submission status: Time Limit Exceeded

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

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

print(answer)

Submission status: Time Limit Exceeded

Solution code:
s = input()
i = 0

ln = len(s)
cnt = 0
if ln >= 4:
    for i in range(0, ln-3, 1):
        for j in range(i+3, ln+1, 1):
            sstr = ''
            for k in range(i, j, 1):
                sstr = sstr + s[k]
            if int(sstr) % 2019 == 0:
                cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
a = []
count = 0
for n in range(len(S)):
    a.append(10**n%2019)
for n in range(len(S)-3):
    z = int(S[-n-1])*a[0]+int(S[-n-2])*a[1]+int(S[-n-3])*a[2]+int(S[-n-4])*a[3]
    if z%2019 == 0:
        count += 1
    for m in range(len(S)-n-4):
        z += int(S[-m-n-5])*a[m+4]
        if z%2019 == 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
#N, K = map(int, input().split())
# 文字列の入力
s = input()
N = len(s)
#print(N)

i = 0
j = 4

ans=0

while(i < N-3):
    while(j<N+1):
        #print(s[i:j])
        #print(int(s[i:j])%2019)
        if int(s[i:j])%2019 == 0:
            ans=ans+1
        j=j+1
        #elif (int(s[i:j])%2019)%1000 == 201:
            #j=j+1
        #elif (int(s[i:j])%2019)%100 == 20:
            #j=j+2
        #elif (int(s[i:j])%2019)%10 == 2:
            #j=j+3
        #else:
            #j=j+4

    i=i+1
    j=i+4

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#A

#デバッグ
debug=1
def pront(*n):
    if debug==1:
        print(n)
        
#10**9+7を底とした処理

base=10**9+7

def add(a,b):#a+b
    return (a+b)%base

def sub(a,b):#a-b
    return (a-b)%base

def multi(a,b):#a*b
    return (a*b)%base

def exp(a,b):#a**b
    x=1
    c=a
    d=b
    while d!=0:
        if d%2==1:
            x=multi(x,c)
        c=(c**2)%base
        d=d//2
    return x

def div(a,b):#a/b
    return(multi(a,exp(b,base-2)))

#入力

S=input()

#処理
L=len(S)
x=0
xx={}
for i in range(5,L+1):
    for j in range(L-i+1):
        if S[j:j+i] in xx:
            xx[S[j:j+i]]+=1
        else:
            xx[S[j:j+i]]=1

for i,j in xx.items():
    if int(i)%2019==0:
        x+=j
print(x)

Submission status: Time Limit Exceeded

Solution code:
s = input()
cnt = 0
for i in range(len(s) - 3):
    for j in range(i + 3, len(s)):
        num = int(s[i:j+1])
        if num < 2019:
            continue
        if num % 3 != 0:
            continue
        if num % 673 != 0:
            continue
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())

mod = [0] * (2019+1)

tmp = ""
for i in range(1, len(S)+1):
    tmp = S[-i] + str(tmp)
    mod[int(tmp) % 2019] += 1

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
x =input()
count = 0
while(True):
    for i in range(99999999999):
        count += x.count(str(2019*i))
    if 2019*i > x:
        break
print(count)