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

import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

dp=[  [ 0 for i in range(K+1) ]  for n in range(N+1) ]
dp[0][0]=1

mod=10**9+7


for n in range(N):
	a=A[n]  #ame
	for k in range(K+1):
		if dp[n][k]!=0:
			for j in range(a+1):	#ame
				if 0<=k+j<=K:
					dp[n+1][k+j]+=dp[n][k]

print dp[N][K]%mod

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())


mod=10**9+7

T=[1]
for a in A:
	W=[0]		#WA:累積和
	l=len(T)
	for j,x in enumerate(T):
		if j==0:	W.append( x%mod )
		else:	W.append( (W[-1]+x)%mod )

	T=[]  #Temporary
	for k in range( min (K+1,a+l) ):
		#print k, min( k+1, l), max(0,k-a), W[min( k+1, l)]-W[max(0,k-a)]
		T.append( W[min( k+1, l)]-W[max(0,k-a)] )


try:
	print T[K]%mod
except IndexError:
	print 0
### BUGGY CODE ###

#D問題
#Bellman-Ford法(最短距離)
def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0
    #辺の緩和
    for i in range(num_v):
        for edge in edges:
            if dist[edge[0]-1] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
    return dist

N,M = map(int,input().split())
ABC = []
for i in range(M):
    a,b,c = map(int,input().split())
    ABC.append([a,b,-c])
    
Dist = BellmanFord(ABC,N,1)

negative = [False for i in range(N)]
inf = float("inf")
for i in range(N):
    for j in range(M):
        if Dist[ABC[j][0]-1] == inf:
            continue
        if Dist[ABC[j][1]-1] > Dist[ABC[j][0]-1]+ABC[j][2]:
            Dist[ABC[j][1]-1] = Dist[ABC[j][0]-1]+ABC[j][2]
            negative[ABC[j][1]-1] = True
            
        if negative[ABC[j][0]-1] == True:
            negative[ABC[j][1]-1] = True


if negative[N-1]:
    print("inf")
else:
    print(-Dist[-1])
    


### FIXED CODE ###

#D問題
#Bellman-Ford法(最短距離)
def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0
    #辺の緩和
    for i in range(num_v):
        for edge in edges:
            if dist[edge[0]-1] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
    return dist

N,M = map(int,input().split())
ABC = []
for i in range(M):
    a,b,c = map(int,input().split())
    ABC.append([a,b,-c])
    
Dist = BellmanFord(ABC,N,1)

negative = [False for i in range(N)]
inf = float("inf")
for i in range(N):
    for j in range(M):
        if Dist[ABC[j][0]-1] == inf:
            continue
        if Dist[ABC[j][1]-1] > Dist[ABC[j][0]-1]+ABC[j][2]:
            Dist[ABC[j][1]-1] = Dist[ABC[j][0]-1]+ABC[j][2]
            negative[ABC[j][1]-1] = True
            
        if negative[ABC[j][0]-1] == True:
            negative[ABC[j][1]-1] = True


if negative[N-1]:
    print("inf")
else:
    print(-Dist[-1])
### BUGGY CODE ###

def maxHeapify(A, i, n):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < n and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < n and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(A, largest, n)
def insert(S, k):
    S.append(k)
    n = len(S)
    i = n - 1
    while i > 0 and S[i] > S[(i - 1) // 2]:
        S[i], S[(i - 1) // 2] = S[(i - 1) // 2], S[i]
        i = (i - 1) // 2
def extractMax(S):
    if len(S) == 1:
        return S.pop()
    ans = S[0]
    S[0] = S.pop()
    maxHeapify(S, 0, len(S))
    return ans
A = []
while True:
    s = input()
    if s == "end":
        break
    elif s == "extract":
        print(extractMax(A))
    else:
       insert(A, int(s[7:]))



### FIXED CODE ###

import sys
from heapq import heapify, heappush, heappop
hq = []
S = []
for s in sys.stdin:
    if s[2] == "s":
        heappush(hq, -int(s[7:]))
    elif s[2] == "t":
        S.append(-heappop(hq))
    else:
        break
print("\n".join(map(str, S)))
### BUGGY CODE ###

n,k=map(int, input().split())
h=[int(input()) for i in range(n)]
h.sort()
ans = h[-1]
for i in range(n-k+1):
  ans = min(ans, max(h[i:i+k])-min(h[i:i+k]))
print(ans)

### FIXED CODE ###

n,k=map(int, input().split())
h=[int(input()) for i in range(n)]
h.sort()
ans = h[-1]
for i in range(n-k+1):
  ans = min(ans, h[i+k-1]-h[i])
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
#from numba import jit

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

#@jit
def gg(nn, x, y, n, is_sit):
	q = deque()
	q.append(1000*x+y)
	cl = set()
	cl.add(x*1000+y)
	while q:
		v = q.popleft()
		x,y = v//1000, v %1000
		nn[x][y] -= 1
		k = nn[x][y]
		for dx,dy in ([-1,0], [0,-1], [1,0], [0,1]):
			if x+dx < 0 or x +dx >= n or y + dy < 0 or y + dy >= n:
				continue
			if nn[x+dx][y + dy] <= k + is_sit[x+dx][y+dy]:
				continue
			if (x+dx)*1000+(y+dy) in cl:
				continue
			q.append((x+dx)*1000+ (y+dy))
			cl.add((x+dx)*1000 + (y+dy))
		#print('yyyyyy')
		#for l in nn:
		#	print(l)

def main():
	n = int(input())
	nn = [[(n+1)//2] * n for _ in range(n)]
	is_sit = [[1] * n for _ in range(n)]
	for i in range(n):
		for j in range(n):
			nn[i][j] = min(i+1,j+1,n-i,n-j)
	#for l in nn:
	#	print(l)
	
	#b , c = tin()
	pl = lin()
	ans = 0
	for p in pl:
		x, y = (p-1) // n, (p-1) % n
		ans += nn[x][y]-1
		is_sit[x][y] = 0
		gg(nn, x, y, n, is_sit)
		
	print(ans)
	#s = input()
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

#+++++

def main():
	n = int(input())
	nn = [[min(i,j,n-i-1,n-j-1) for j in range(n)] for i in range(n)]
	is_sit = [[True] * n for _ in range(n)]
	cc = [[0]*n for _ in range(n)]
	
	#b , c = tin()
	pl = list(map(int, input().split()))
	ans = 0
	for p in pl:
		x, y = (p-1) // n, (p-1) % n
		ans += nn[x][y]
		is_sit[x][y] = False
		q = [(x, y, nn[x][y])]
		while q:
			(x, y, v) = q.pop()
			if x >= 0 and nn[x-1][y]>v:
				nn[x-1][y] = v
				q.append((x-1, y, v+is_sit[x-1][y]))
			if x < n-1 and nn[x+1][y]>v:
				nn[x+1][y] = v
				q.append((x+1, y, v+is_sit[x+1][y]))		
			if y >= 0 and nn[x][y-1]>v:
				nn[x][y-1] = v
				q.append((x, y-1, v+is_sit[x][y-1]))
			if y < n-1 and nn[x][y+1]>v:
				nn[x][y+1] = v
				q.append((x, y+1, v+is_sit[x][y+1]))	
		
	print(ans)
	#s = input()	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

def main():
    n = int(input())
    sl = [ list(input()) for _ in range(n) ]
    ans = 0

    
    for i in sl:
        i.sort() #sort() methodは元を変える
    
    st = tuple(sl)
    
    for i in range(len(st)-1):
        for j in range(i+1,len(st)):
            if sl[i] == sl[j]:
                ans += 1

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

A ={}
c = 0
for i in range(int(input())):
    a = str(sorted(input()))
    if a in A:
        A[a] += 1
        c += A[a]
    else:
        A[a] = 0
print(c)
### BUGGY CODE ###

n=int(input())
r=range(1,int(2*n**.5)+1)
l=[0]*-~n
for i in r:
  for j in r:
    for k in r:
      t=(j+k)**2+(k+i)**2+(i+j)**2
      if t<=n*2 and t%2<1: l[t//2]+=1
for i in range(n): print(l[i+1])

### FIXED CODE ###

n=int(input())
r=range(1,int((2*10**4)**.5)+1)
l=[0]*-~n
for i in r:
  for j in r:
    for k in r:
      t=(j+k)**2+(k+i)**2+(i+j)**2
      if t<=n*2 and t%2<1:
        l[t//2]+=1
for i in range(n): print(l[i+1])
### BUGGY CODE ###

def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def merge(left, mid, right):
    L = []+S[left:mid]
    R = []+S[mid:right]
    x = []
    c = right - left
    lp = 0
    rp = 0
    fa = 0
    fb = 0
    while True:
        if fa==0:
            try:
                a = L[lp]
            except:
                break
            lp += 1
            fa = 1
        if fb == 0:
            try:
                b = R[rp]
            except:
                break
            rp += 1
            fb =1
        if a < b:
            x.append(a)
            fa = 0
        else:
            x.append(b)
            fb =0
    if fa ==0:
        x.extend(R[rp-1:])
    else:
        x.extend(L[lp-1:])
    S[left:right] = x
    return c

def mergesort(left, right):
    c = 0
    if left + 1 < right:
        mid = (left + right)/2
        c += mergesort(left, mid)
        c += mergesort(mid, right)
        c += merge(left, mid, right)
    return c

global S
n = f()
S = f2()

c = mergesort(0, n)
print " ".join(map(str,S))
print c

### FIXED CODE ###

def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    lp, rp, xp = 0, 0, 0
    a, b = L[0], R[0]
    c = right - left
    x = [0] * c
    flg = True
    while flg:
        while flg and a <= b:
            x[xp] = a
            lp += 1
            xp += 1
            try:
                a = L[lp]
            except:
                for e in R[rp:]:
                    x[xp] = e
                    xp += 1
                flg = False
        while flg and a >= b:
            x[xp] = b
            rp += 1
            xp += 1
            try:
                b = R[rp]
            except:
                for e in L[lp:]:
                    x[xp] = e
                    xp += 1
                flg = False
    S[left:right] = x
    return c

def mergesort(left, right):
    c = 0
    if left + 1 < right:
        mid = (left + right)/2
        c += mergesort(left, mid)
        c += mergesort(mid, right)
        c += merge(left, mid, right)
    return c

global S
n = f()
S = f2()

c = mergesort(0, n)
print " ".join(map(str,S))
print c
### BUGGY CODE ###

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.9998
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
    b,c=map(int,input().split())
    a+=[c]*b
    a.sort(reverse=True)
    a=a[:n]
print(sum(a))

### FIXED CODE ###

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

N = int(input())
lResult = [input() for i in range(N)]
lGain = []

for i in range(N):
    for j in range(len(lGain)):
        if lResult[i] == lGain[j]:
            break
    else:
        lGain.append(lResult[i])

print(len(lGain))

### FIXED CODE ###

N = int(input())
lResult = [input() for i in range(N)]

gain = list(set(lResult))

print(len(gain))
### BUGGY CODE ###

import math

A, B, N = map(int, input().split())
mx = 0
p = N
q = B

if B <= N:
    mx = math.floor(A / B * q) - math.floor(q / B) * A
    while mx == 0:
        q -= int(B / 20)
else:
    mx = math.floor(A / B * p) - math.floor(p / B) * A
    while mx == 0:
        p -= int(N / 20)

print(mx)

# for x in range(1, 35):
#     print(math.floor(9 /23 * x) - math.floor(x / 23) * 9)

### FIXED CODE ###

import math

A, B, N = map(int, input().split())

if N >= B-1:  # x = B-1のときに最大値
    beta = (B-1)/B
    print(math.floor(A * beta))

else:
    beta = N/B
    print(math.floor(A * beta))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [ x for x in set(a) if a.count(x)>1]
c = [ x for x in set(a) if a.count(x)>3]
b.sort()
c.sort()
m = len(b)
if m<2:
    if len(c)<1:
        print(0)
    else:
        print(c[-1]*c[-1])
else:
    if len(c)<1:
        print(b[-1]*b[-2])
    else:
        ans = max(b[-2]*b[-1],c[-1]*c[-1])
        print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
i = 1
j = 1
l = []
while i<n:
    if a[i]==a[i-1]:
        l.append(a[i])
        i+=2
    else:
        i+=1
l.append(0)
l.append(0)
print(l[0]*l[1])
### BUGGY CODE ###

a = int(input())
ar = list(map(int,input().split(" ")))
for i in range(a):
    print(ar.count(i+1))

### FIXED CODE ###

a = int(input())
ar = list(map(int,input().split(" ")))
br = [0 for i in range(a)]
for r in ar:
    br[r-1] += 1
for r in br:
    print(r)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

E = []
for i in range(X):
    for j in range(Y):
        E.append(A[i]+B[j])
        
E = sorted(E, reverse=True)[:K]

F = []
for k in range(len(E)):
    for l in range(Z):
        F.append(E[k]+C[l])

F = sorted(F, reverse=True)

for i in range(K):
    print(F[i])

### FIXED CODE ###

import heapq
 
X, Y, Z, K = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse=True)
B = sorted([int(i) for i in input().split()], reverse=True)
C = sorted([int(i) for i in input().split()], reverse=True)
 
heap = []
heapq.heappush(heap, (-(A[0] + B[0] + C[0]), 0, 0, 0))
added = set([(0, 0, 0)])
for _ in range(K):
    p, i, j, k = heapq.heappop(heap)
    if (i + 1, j, k) not in added and i + 1 < X:
        heapq.heappush(heap, (-(A[i + 1] + B[j] + C[k]), i + 1, j, k))
        added.add((i + 1, j, k))
    if (i, j + 1, k) not in added and j + 1 < Y:
        heapq.heappush(heap, (-(A[i] + B[j + 1] + C[k]), i, j + 1, k))
        added.add((i, j + 1, k))
    if (i, j, k + 1) not in added and k + 1 < Z:
        heapq.heappush(heap, (-(A[i] + B[j] + C[k + 1]), i, j, k + 1))
        added.add((i, j, k + 1))
    print(-p)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    A, B, N = map(int, input().split())

    num = N//B

    score = 0
    for x in range(1, N+1):
        tmp = int(A*x/B) - A*int(x/B)
        if score <= tmp:
            score = tmp
    print(score)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    A, B, N = map(int, input().split())

    x = min(B-1, N)
    print(int(A*x/B)-A*int(x/B))


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import bisect

N, M, K = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
cmplst = a
index = 0
for i in range(M):
    tmp = bisect.bisect_right(cmplst[index:], b[i])
    cmplst.insert(tmp + index, b[i])
    index = tmp

rui = [0] * (N + M + 1)
for i in range(N + M):
    rui[i + 1] = cmplst[i] + rui[i]

tmp = bisect.bisect_left(rui, K)
if rui[tmp] == K:
    print(tmp)
else:
    print(tmp - 1)

### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)

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

n=int(input())
s=[]
for _ in range(n):
    x=list(input())
    x.sort()
    x="".join(x)
    s.append(x)
cnt=0
for _ in range(n):
    a=s.pop(-1)
    for i in s:
      if i==a:
        cnt += 1
    else:
        pass
print(cnt)

### FIXED CODE ###

from collections import Counter
n=int(input())
v=[]
for i in range(n):
	s=list(input())
	s.sort()
	v.append(''.join(s))
c=dict(Counter(v))
ans=0
for i in c.values():
	ans+=(i*(i-1))//2
print(ans)
### BUGGY CODE ###

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
ans=0
k=int(input())
for x in range(1,k+1):
    for y in range(1,k+1):
        for z in range(1,k+1):
            ans+=gcd(x,gcd(y,z))
print(ans)

### FIXED CODE ###

from math import gcd
k=int(input())
ans=0
for l in range(1, k+1):
  for m in range(1, k+1):
    for n in range(1, k+1):
      ans+=gcd(l,gcd(m,n))
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    p = list(map(float, input().split()))

    dp = [[0.0 for i in range(n + 1)] for j in range(n + 1)]
    dp[0][0] = 1.0
    for i in range(n):
        for j in range(n):
            dp[i + 1][j + 1] += dp[i][j] * p[i]
            dp[i + 1][j] += dp[i][j] * (1.0 - p[i])

    ans = 0.0
    for i in range(n // 2+1, n+1):
        ans += dp[n][i]
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    p = list(map(float, input().split()))

    dp = [[0.0 for i in range(n + 1)] for j in range(n + 1)]
    dp[0][0] = 1.0
    for i in range(n):
        for j in range(n):
            dp[i + 1][j + 1] += dp[i][j] * p[i]
            dp[i + 1][j] += dp[i][j] * (1.0 - p[i])

    ans = 0.0
    for i in range(n // 2+1, n+1):
        ans += dp[n][i]
    print(ans)


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

X = int(input())
Acount = 0
Bcount = 0
di= {}
def func(i):
    return i**5
for i in range(3000):
    di[str(func(i))] = str(i)
preA = int(X **(1/5))
while True:
    funcA = preA**5
    if funcA-X>=0 and str(funcA-X) in di.keys():
        print(str(preA)+" "+di[str(funcA-X)])
        break
    elif X-funcA>= 0 and str(X-funcA) in di.keys():
        print(str(preA)+" -"+di[str(X-funcA)])
        break
    preA += 1

### FIXED CODE ###

X = int(input())
Acount = 0
Bcount = 0
di= {}
def func(i):
    return i**5
for i in range(5000):
    di[str(func(i))] = str(i)
preA = int(X **(1/5))-1000
while True:
    funcA = preA**5
    if funcA-X>=0 and str(funcA-X) in di.keys():
        print(str(preA)+" "+di[str(funcA-X)])
        break
    elif X-funcA>= 0 and str(X-funcA) in di.keys():
        print(str(preA)+" -"+di[str(X-funcA)])
        break
    preA += 1
### BUGGY CODE ###

import sys
from collections import deque
from collections import defaultdict
import math
import copy
#input = sys.stdin.readline
sys.setrecursionlimit(20000000)
s = input()
n = len(s)
dp = [[0]*2019 for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = 1
for i in range(n):
    for j in range(2019):
        dp[i+1][(j*10+int(s[i]))%2019] += dp[i][j]
ans = 0
for i in range(n+1):
    ans += dp[i][0]
print(ans-n-1)


### FIXED CODE ###

import sys
from collections import deque
from collections import defaultdict
import math
import copy
#input = sys.stdin.readline
sys.setrecursionlimit(20000000)
s = input()
s = s[::-1]
n = len(s)
dp = [0]*(n+1)
k = 1
a = defaultdict(int)
a[0]+=1
for i in range(n):
  dp[i] = (dp[i-1]+int(s[i])*k)%2019
  k*=10
  k%=2019
  a[dp[i]] += 1
ans = 0
for i in a.keys():
  ans += a[i]*(a[i]-1)/2
print(int(ans))
### BUGGY CODE ###

h,w,n=map(int,input().split())
s={tuple(map(int,input().split())) for _ in range(n)}
p=[(i,j) for i in (-1,0,1) for j in (-1,0,1)]
t={(a+i,b+j) for a,b in s for i,j in p}
c=[0]*10
for a,b in t:
    if 2<=a<=h-1 and 2<=b<=w-1:
        c[sum((a+i,b+j) in s for i,j in p)]+=1
c[0]=(h-2)*(w-2)-sum(c)
for i in c:
    print(i)

### FIXED CODE ###

h,w,n=map(int,input().split())
d={}
for _ in range(n):
    a,b=map(int,input().split()) 
    for i in (-1,0,1):
        for j in (-1,0,1):
            if 2<=a+i<=h-1 and 2<=b+j<=w-1:
                d.setdefault((a+i,b+j),0)
                d[a+i,b+j]+=1
r=[0]*10
for i in d.values():
    r[i]+=1
r[0]=(h-2)*(w-2)-sum(r)
for i in r:
    print(i)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from math import factorial 
def main():
    x, y = map(int, readline().split())
    if ((2*y-x)%3) or ((2*x-y)%3):
        print(0)
        return
    a = (2*y-x)//3
    b = (2*x-y)//3
    if a < 0:
        print(0)
        return
    if b < 0:
        print(0)
        return
    P = int(1e9)+7
    def c(n, m):
        ch = 1
        for i in range(m):
            ch *= (n-i)
            ch %= P
        b_ = factorial(m) 
        b = pow(b_, P-2, P)
        return ch*b%P
    print(c(a+b, a)) 
if __name__ == '__main__':
    main()


### FIXED CODE ###

#python3
from math import factorial
from math import floor
MOD = int(1e9+7)

def comb(n, m, mod):
    comb_a = 1
    for i in range(m): 
        comb_a *= (n-i)
        comb_a %= mod
    comb_tmp = factorial(m) 
    comb_b = pow(comb_tmp, mod-2, mod)
    return (comb_a * comb_b)%mod
def main():
    x, y = map(int, input().split())
    k = (2*x-y)/3
    l = (2*y-x)/3

    if floor(k) - k != 0:
        print(0)
        return
    if floor(l) - l != 0:
        print(0)
        return 
    if k<0:
        print(0)
        return
    if l<0:
        print(0)
        return
    k = int(k)
    l = int(l)
    print(comb(k+l, k, MOD)%MOD) 

main()