Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from itertools import accumulate

MOD = 10**9+7

n, c = map(int, input().split())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
E = [[0]*(c+1) for _ in range(n)]
for j in range(c+1):
  cumsum = tuple(pow(k, j, MOD) for k in range(401))
  cumsum = tuple(accumulate(cumsum))
  for i, (a, b) in enumerate(zip(A, B)):
    E[i][j] = cumsum[b] - cumsum[a-1]

dp = [[0]*(c+1) for _ in range(n+1)]
dp[0][0] = 1
for i, e in enumerate(E):
  for j, f in enumerate(e):
    for k in range(c+1):
      if j+k <= c:
        dp[i+1][j+k] += dp[i][k]*f
        dp[i+1][j+k] %= MOD
ans = dp[n][c]
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from itertools import accumulate

MOD = 10**9+7

n, c = map(int, input().split())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
E = [[0]*(c+1) for _ in range(n)]
for j in range(c+1):
  cumsum = tuple(pow(k, j, MOD) for k in range(401))
  cumsum = tuple(i%MOD for i in accumulate(cumsum))
  for i, (a, b) in enumerate(zip(A, B)):
    E[i][j] = cumsum[b] - cumsum[a-1]

dp = [[0]*(c+1) for _ in range(n+1)]
dp[0][0] = 1
for i, e in enumerate(E):
  for j, f in enumerate(e):
    for k in range(c+1):
      if j+k <= c:
        dp[i+1][j+k] += dp[i][k]*f
        dp[i+1][j+k] %= MOD
ans = dp[n][c]
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
s = (input())

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


### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections
s = (input())

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

n = len(s)
ans = 0
l = 0
#r = l
num = int(s)

tmp = [0 for _ in range(n+1)]
ten = [0 for _ in range(n)]
tmp1 = 0
val = 1
for i in range(0,n):
    ten[i] = val
    tmp1 += (int(s[n-i-1]) * val)
    tmp[i+1] = tmp1 % 2019
    val = (val * 10) % 2019
#print(tmp)

c = collections.Counter(tmp)
#print(c)
for i in range(0, 2020):
    a = c[i]
    if a > 0:
        ans += ((a * (a - 1)) // 2)
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
f=[int(i) for i in input().split()]

a.sort()
f.sort(reverse=True)

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        sup = x//F
        if sup < A:
            syugyo += A-sup
    if syugyo <= k:
        return True
    else:
        return False


left = 0
right = a[-1]*f[0]+1
while left < right-1:
    mid = (left+right)//2
    if score(mid):
        right = mid
    else:
        left = mid
print(left+1 if left != 0 else 0)

### FIXED CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
f=[int(i) for i in input().split()]

# aとfの組み合わせはソートして逆向きが最適
# 帰納法で示す

# チームの成績x→単に成績x,メンバーiの成績→xi

# 0<=x<=a[-1]*f[0]な整数xがあったら
# 成績x以下にすることはできるか？という命題を考える

# gi=int(x/fi)は食べ物iで成績xiを出せる最大値
# 　aiがgiを超えてしまうと成績xi以下は修行しないと出せない
# 　ai<=giならその人の成績はxi以下になる
# なのでmax(ai-gi,0)は成績xi以下であるために必要な修行の回数

# よってsum=Σmax(ai-gi,0)は成績x以下を達成するのに、必要なチーム全体の総修行回数
# したってsum<=Kなら成績x以下にすることができる

# 各整数について命題はFalseかTrueを返す
# その順番は1から順にF...FT...Tとなる
# この一番左のTの整数xが求めたい最小値：チームの成績xの最小値

a.sort()
f.sort(reverse=True)

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        syugyo += max(A-int(x/F),0)
    if syugyo <= k:
        return True
    else:
        return False


left = 0
right = a[-1]*f[0]+1
while left < right-1:
    mid = (left+right)//2
    if score(mid):
        right = mid
    else:
        left = mid
print(left+1 if left != 0 else 0)
    
# 計算量は 1+2logN + N*log(2)N <= N*logN < 3.6 * 10^6 
# ぎりぎりセーフ？
### BUGGY CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
narr = lambda d, f: narr(d[:-1], lambda: [f() for _ in range(d[-1])]) if d else f() # narr((2,3), int)
mod = 1000000007
sys.setrecursionlimit(1000000)

H, W = rl()
C = rl()
D = rl()
M = []
for i in range(H):
	s = rs()
	M.append(s)

start = tuple([C[0]-1, C[1]-1])
end = tuple([D[0]-1, D[1]-1])

queue = deque()
queue.append((start, 0))
visited = narr((H, W), lambda: float('inf'))
visited[start[0]][start[1]] = 0

ds = [(1,0),(-1,0),(0,1),(0,-1)]
while queue:
	n, d = queue.popleft()
	if n == end:
		print(d)
		exit()
	i, j = n
	if visited[i][j] != d:
		continue
	nd = d
	for di, dj in ds:
		ni, nj = i+di, j+dj
		if not (0 <= ni < H and 0 <= nj < W): continue
		if M[ni][nj] == '#': continue
		if nd < visited[ni][nj]:
			queue.appendleft(((ni,nj), nd))
			visited[ni][nj] = nd
	nd = d+1
	for di in range(-2, 3):
		for dj in range(-2, 3):
			if (di, dj) == (0,0): continue
			ni, nj = i+di, j+dj
			if not (0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '#': continue
			if nd < visited[ni][nj]:
				queue.append(((ni,nj), nd))
				visited[ni][nj] = nd
print(-1)


### FIXED CODE ###

import sys, math
from collections import defaultdict, deque, Counter
#from bisect import bisect_left, bisect_right
#from itertools import combinations, permutations, product
from heapq import heappush, heappop
#from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

dist = defaultdict(lambda: float('inf'))
def dijkstra(start, end):
	dist[start] = 0
	heap = []
	heappush(heap, (0, start))
	while heap:
		d, n = heappop(heap)
		if n == end:
			return d
		if dist[n] != d:
			continue
		edges = get_edges(n)
		for nn, ed in edges:
			nd = d + ed
			if dist[nn] > nd:
				dist[nn] = nd
				heappush(heap, (nd, nn))
	return -1

def get_edges(n):
	i, j = n
	edges = []
	if M[i][j] == '#': return edges
	for di in range(-2, +3):
		for dj in range(-2, +3):
			ni, nj = i+di, j+dj
			if di == 0 and dj == 0: continue
			if not(0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '#': continue
			if (di, dj) in [(1,0),(-1,0),(0,1),(0,-1)]:
				edges.append(((ni, nj), 0))
			else:
				edges.append(((ni, nj), 1))
	return edges

H, W = rl()
C = rl()
D = rl()
M = []
for i in range(H):
	s = rs()
	M.append(s)

start = tuple([C[0]-1, C[1]-1])
end = tuple([D[0]-1, D[1]-1])
d = dijkstra(start, end)
print(d)
### BUGGY CODE ###

N, M = map(int, input().split())
L = [0] * M
R = [0] * M
for i in range(M):
    L[i], R[i] = map(int, input().split())

all_lists = [list(range(L[i], R[i] + 1)) for i in range(M)]

new_set = set(all_lists[0])
for i in range(len(all_lists) - 1):
    new_set = new_set & set(all_lists[i + 1])

print(len(new_set))

### FIXED CODE ###

N, M = map(int, input().split())
L = M * [0]
R = M * [0]
for i in range(M):
    Left, Right = map(int, input().split())
    L[i] = Left
    R[i] = Right

L_max = max(L)
R_min = min(R)

count = 0
for i in range(1, N + 1):
    if i >= L_max and i <= R_min:
        count += 1
print(count)
### BUGGY CODE ###

H,W,A,B = map(int,input().split())
mod = 10**9+7
def comb(a,b,p):
    if a<0 or b<0 or a<b: return 0
    if a==0 or b==0: return 1
    fa = 1
    fb = 1
    fab = 1
    for i in range(1,a+1):
        fa = (fa*i)%p
    for i in range(1,b+1):
        fb = (fb*i)%p
    for i in range(1,a-b+1):
        fab = (fab*i)%p
    return (fa*power2(fb,p-2,p)*power2(fab,p-2,p))%p
def power2(a,b,p):
    if b == 0:
        return 1
    if b%2 == 0:
        d = power2(a,b//2,p)
        return (d*d)%p
    return (a*power2(a,b-1,p))%p
ans = 0
for w in range(B,W):
    ans = (ans+ (comb(H-A+w-1,w,mod)*comb(A+W-w-2,A-1,mod))%mod)%mod
print(ans)

### FIXED CODE ###

H,W,A,B = map(int,input().split())
mod = 10**9+7
x1 = [1 for i in range(H+W)]
xi = [1 for i in range(H+W)]
num = 1
def power2(a,b,p):
    if b == 0:
        return 1
    if b%2 == 0:
        d = power2(a,b//2,p)
        return (d*d)%p
    return (a*power2(a,b-1,p))%p
for i in range(1,H+W):
    num = (num*i)%mod
    x1[i] = num
for i in range(1,H+W):
    x2 = power2(x1[i],mod-2,mod)
    xi[i] = x2
def comb(a,b,p):
    return (x1[a]*xi[b]*xi[a-b])%p
ans = 0
for w in range(B,W):
    ans = (ans+ (comb(H-A+w-1,w,mod)*comb(A+W-w-2,A-1,mod))%mod)%mod
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python

import sys
from math import log

s= sys.stdin.readline().strip()
n= len(s)
steps= [ [0]*n for i in range(333) ]
ref= steps[0]
for i in range(n):
    if s[i]=="L": ref[i]= i-1
    if s[i]=="R": ref[i]= i+1
#
for i in range(1,333):
    sp = steps[i-1]
    sn = steps[i]
    for j in range(n): sn[j]= sp[sp[j]]
#
table = [False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, True, False, False, False, True, True, True, True, False, False, False, True, False, True, True, True, False, True, False, False, False, False, False, True, False, True, False, True, False, False, False, True, False, False, False, False, True, True, False, False, False, False, True, False, False, True, False, False, True, True, False, True, False, True, False, True, False, True, False, True, False, False, True, True, True, True, True, False, False, True, False, True, True, False, False, False, True, False, False, False, False, True, False, False, False, True, True, True, False, False, False, True, False, False, False, False, False, False, True, False, False, True, True, True, False, False, True, True, False, True, False, True, False, False, False, True, True, True, False, False, True, True, True, True, True, True, False, True, False, False, False, False, False, True, True, True, False, False, True, True, False, False, True, False, False, False, True, True, False, False, True, False, False, False, False, True, True, True, True, False, False, True, False, False, True, True, False, True, False, False, False, False, True, True, False, True, False, True, True, True, False, False, True, True, True, True, True, False, True, True, False, False, False, False, True, True, False, False, True, False, True, False, False, True, True, False, True, False, False, True, False, False, True, False, True, True, False, True, False, True, True, False, False, True, False, False, True, False, False, True, False, False, True]
#
now= [ i for i in range(n) ]
for i in range(333):
    if table[i]:
        tmp= now.copy()
        now= [ steps[i][tmp[j]] for j in range(n) ]
#
for i in range(n):
    print( now.count(i),end=" " )


### FIXED CODE ###

import sys

s0=[]
for i,c in enumerate(sys.stdin.readline().strip()):
    if c=="L": s0.append(i-1)
    if c=="R": s0.append(i+1)
n= len(s0)
#
now= [ i for i in range(n) ]
prev= s0
for i in range(17):
    now = [ prev[i] for i in prev ]
    prev= now
#
ans= [0]*n
for i in range(n): ans[now[i]]+=1
for i in range(n): print( ans[i],end=" " )
### BUGGY CODE ###

from collections import deque

Y, X = map(int,input().split())
# sy, sx = map(int, input().split())
# gy, gx = map(int, input().split())
sy,sx = 1,1
gy,gx = Y,X
s = [["#"]*(X+2) for _ in range(Y+2)]
for y in range(Y):
    s[y+1] = list("#"+input()+"#")
inf = Y*X
c = [[inf]*X for _ in range(Y)]
c[sy-1][sx-1] = 0
drs = [(-1,0),(1,0),(0,-1),(0,1)]
q = deque([(sy-1, sx-1)])

while q:
    y,x = q.popleft()
    cost = c[y][x]
    for dx,dy in drs:
        x2 = x+dx
        y2 = y+dy
        if s[y2+1][x2+1] == "." and c[y2][x2] > cost:
            c[y2][x2] = cost+1
            q.appendleft((y2,x2))
if c[gy-1][gx-1] == inf:
    print("-1")
else:
    dots = 0
    for s1 in s:
        dots +=s1.count(".")
    print(dots-c[gy-1][gx-1]-1)

### FIXED CODE ###

H, W = map(int,input().split())
c = [["#"]*(W+2) for _ in range(H+2)]
dots = 0
for y in range(H):
    c[y+1] = "#",*list(input()),"#" 
    dots += c[y+1].count(".")
inf = H*W
m = [[inf]*W for _ in range(H)]
m[0][0] = 0
drs = [[-1,0],[1,0],[0,-1],[0,1]]

s = 0
yx = [[1, 1]]
notgoal = True
while notgoal and yx:
    yx2 = []
    s += 1
    for y,x in yx:
        for dy, dx in drs:
            x2 = x+dx
            y2 = y+dy
            if c[y2][x2] == "." and m[y2-1][x2-1] == inf:
                m[y2-1][x2-1] = s
                if (y2,x2) == (H,W):
                    notgoal = False
                else:
                    yx2.append([y2, x2])
    yx = yx2

if notgoal:
    print("-1")
else:
    print(dots-s-1)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    #ビット全探索を行う
    import itertools
    li = list(itertools.product([0, 1], repeat=n)) # ０が不親切もの、１が親切もの

    #dd[i]:人iが人xをy（０なら不親切,１なら親切)だと思っていることを収納
    from collections import deque, defaultdict
    dd = {}
    for i in range(n):
        dd[i] = deque()
    for i in range(n):
        a = int(input())
        for j in range(a):
            x, y = map(int, input().split())
            dd[i].append((x-1, y))


    from copy import deepcopy
    max_sum = 0 #親切者の数の最大値
    for i in li: # i には親切者のタプルが入っている
        ppp = 0
        for ggg in i:
            ppp += ggg
        if ppp <= max_sum:
            continue
        sum_ = 0
        co = deepcopy(dd)
        vv = 0
        for k in range(len(i)): #全員の証言が矛盾しないかを考える
            if i[k] == 0: # 不親切ものの場合
                continue
            else: #以下k人目の証言を考える
                sum_ += 1
                length = len(co[k])
                c = 0
                while co[k]:
                    x, y = co[k].popleft()
                    if i[x] != y: #証言と一致していない場合
                        break
                    else:
                        c+=1
                if c == length: #k人目の証言が全てあっている場合
                    vv += 1
        if vv == sum_:
            max_sum = max(max_sum, vv)

    print(max_sum)
            
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    #ビット全探索を行う
    import itertools
    li = list(itertools.product([0, 1], repeat=n)) # ０が不親切もの、１が親切もの

    #dd[i][x] = y:人iが人xをy（０なら不親切,１なら親切)だと思っていることを収納
    NIL = -1
    dd = [[NIL]*n for _ in range(n)]
    for i in range(n):
        a = int(input())
        for j in range(a):
            x, y = map(int, input().split())
            x = x-1
            dd[i][x] = y


    from copy import deepcopy
    max_sum = 0 #親切者の数の最大値
    for i in li: # i には親切者のタプルが入っている
        ppp = 0
        for ggg in i:
            ppp += ggg
        if ppp <= max_sum:
            continue
        sum_ = 0
        flag = True
        for k in range(len(i)): #全員の証言が矛盾しないかを考える
            if i[k] == 0: # 不親切ものの場合
                continue
            else: #以下k人目の証言を考える
                sum_ += 1
                for l in range(n):
                    if dd[k][l] != NIL and dd[k][l] != i[l]: #証言と一致していない場合
                        flag = False
                        break
        if flag:
            max_sum = max(max_sum, sum_)

    print(max_sum)
            
if __name__ == '__main__':
    main()
### BUGGY CODE ###

S=input()
unko=[0]*2019
tmp=0
num=1
for s in S[::-1]:
  s=int(s)
  tmp+=num * s
  num=num*10
  unko[tmp%2019]+=1
ans=0
ans+=(unko[0]+1)*unko[0]/2
for i in unko[1:]:
  ans+=i*(i-1)/2
print(int(ans))

### FIXED CODE ###

S=input()
unko=[0]*2019
tmp=0
num=1
for s in S[::-1]:
  s=int(s)
  tmp=(tmp+s*num)%2019
  num=(num*10)%2019
  unko[tmp]+=1
ans=0
ans+=(unko[0]+1)*unko[0]/2
for i in unko[1:]:
  ans+=i*(i-1)/2
print(int(ans))
### BUGGY CODE ###

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

N, K = MAP()
A = LIST()
A = [x-1 for x in A]
D = 60
to = [[0]*N for _ in range(D)]
to[0] = A.copy()

for i in range(D-1):
	for j in range(N):
		to[i+1][j] = to[i][to[i][j]]

v = 0
for i in range(D-1, -1, -1):
	l = 1<<i
	if l <= K:
		v = to[i][v]
		K -= l
print(v+1)


### FIXED CODE ###

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

N, K = MAP()
A = LIST()

cnt = 0
now = 0

visited = [0]*N
while not visited[now]:
	visited[now] = cnt
	cnt += 1
	now = A[now]-1
	if cnt == K:
		print(now+1)
		exit()

K -= visited[now]
K = K%(cnt-visited[now])
visited = [0]*N
for i in range(K):
	now = A[now]-1
print(now+1)
### BUGGY CODE ###

def dist(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

h,w= map(int, input().split())
wh = []
bl = []
for i in range(h):
    li = input()
    for j in range(w):
        if li[j] == '#':
            bl.append((i,j))
        else:
            wh.append((i,j))
ans = 0
for ww in wh:
    m = 1000000
    for bb in bl:
        d = dist(bb, ww)
        if d < m:
            m = d
    if m > ans:
        ans = m
print(ans)


### FIXED CODE ###

h,w= map(int, input().split())
a = []
x = []
for i in range(h):
    li = input()
    aa = []
    for j in range(w):
        aa.append(li[j])
        if aa[j] == '#':
            x.append((i, j))
    a.append(aa)
ans = 0
while True:
    xx = []
    for p in x:
        pp = [(p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1)]
        for ppp in pp:
            if (0 <= ppp[0] < h) and (0 <= ppp[1] < w):
                if a[ppp[0]][ppp[1]] == '.':
                    a[ppp[0]][ppp[1]] = '#'
                    xx.append((ppp[0], ppp[1]))
    x = xx
    if len(x) == 0:
        break
    ans += 1
    # print(x)
print(ans)
### BUGGY CODE ###

N, S = map(int, input().split())
As = list(map(int, input().split()))
mod = 998244353
dp = [[2**i%mod]+[0]*(S) for i in range(N+1)]

for i in range(1, N+1):
    a = As[i-1]
    for s in range(1, S+1):
        if s-a>=0:
            dp[i][s] += (dp[i-1][s-a] + dp[i-1][s]*2)%mod
        else:
            dp[i][s] += (dp[i-1][s]*2)%mod
        dp[i][s] %= mod
print(dp[-1][-1]%mod)

### FIXED CODE ###

N, S = map(int, input().split())
As = list(map(int, input().split()))
mod = 998244353
dp = [[0]*(S+1) for i in range(N+1)]
dp[0][0] = 1
for i in range(1, N+1):
    a = As[i-1]
    for s in range(S+1):
        if s-a>=0:
            dp[i][s] += dp[i-1][s-a] + dp[i-1][s]*2
        else:
            dp[i][s] += dp[i-1][s]*2
        dp[i][s] %= mod
print(dp[-1][-1]%mod)
### BUGGY CODE ###

n,m = map(int,input().split())
*q, = map(int,input().split())
l = []
for _ in range(m):
  b, c = map(int,input().split())
  l.extend([c]*b)
#print(l)
l.sort(reverse=True)
for i in l:
  q.extend([i])
  if len(q) > 2*n:
    break
q.sort(reverse=True)
print(sum(q[:n]))

### FIXED CODE ###

n,m=map(int,input().split())
*q, = map(int,input().split())
#print(q)
l = [list(map(int,input().split())) for _ in range(m)]
l.sort(key=lambda x:x[1], reverse=True)
#print(l)
for b,c in l:
  q.extend([c]*b)
  if len(q) > n*2:
    break

print(sum(sorted(q,reverse=True)[:n]))
### BUGGY CODE ###

import numpy as np

S = input()
MOD = 2019
dp = np.zeros(MOD, dtype=np.int64)
dp[0] = 1

ans = 0
for i, s in enumerate(S[::-1]):
    dp = np.roll(dp, int(s) * pow(10, i, MOD) % MOD)
    ans += dp[0]
    dp[0] += 1
print(ans)


### FIXED CODE ###

from collections import defaultdict
S = input()
MOD = 2019

cnt = [0] * MOD
cnt[0] = 1

now = 0
ans = 0
for d, n in enumerate(map(int, S[::-1])):
    now = (n * pow(10, d, MOD) + now) % MOD
    ans += cnt[now]
    cnt[now] += 1

print(ans)
### BUGGY CODE ###

def inv(a):
    m=10**9+7
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m


def main():
    MOD=10**9+7
    n,k=map(int,input().split())
    a=list(map(int,input().split()))

    frac=[1]
    for i in range(1,n+1):
        frac.append(frac[-1]*i%MOD)


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

    for x in range(a[0]+1):
        dp[0][x]=frac[n]*frac[n-x]*inv(frac[a[0]-x]*frac[n-a[0]]*frac[x])%MOD

    for i in range(k-1):
        ai=a[i+1]
        for j in range(n+1):
            for x in range(ai+1):
                p=j+x
                if p>n: break
                tmp=dp[i][j]
                tmp*=frac[n-x]*inv((frac[ai-x]*frac[n-ai]*frac[x])%MOD)%MOD
                dp[i+1][p]=(dp[i+1][p]+tmp)%MOD
    print(dp[k-1][n]%MOD)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def inv(a):
    m=10**9+7
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m


def main():
    MOD=10**9+7
    n,k=map(int,input().split())
    a=list(map(int,input().split()))

    frac=[1]
    for i in range(1,n+1):
        frac.append(frac[-1]*i%MOD)
    
    fracinv=[inv(frac[i]) for i in range(n+1)]


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

    for x in range(a[0]+1):
        dp[0][x]=frac[n]*frac[n-x]*inv(frac[a[0]-x]*frac[n-a[0]]*frac[x])%MOD

    for i in range(k-1):
        ai=a[i+1]
        for j in range(n+1):
            for x in range(ai+1):
                p=j+x
                if p>n: break
                tmp=dp[i][j]
                tmp=(tmp*frac[n-x]*fracinv[ai-x])%MOD
                tmp=(tmp*fracinv[n-ai]*fracinv[x])%MOD
                dp[i+1][p]=(dp[i+1][p]+tmp)%MOD
    print(dp[k-1][n]%MOD)

if __name__ == "__main__":
    main()