N = int(input())
M = int(input())
N = (N//1000)%M
pascal = [0] * (M+1)
pascal[0] = 1
for i in range(1,M+1):
	for j in range(M,0,-1):
		pascal[j] = (pascal[j-1]+pascal[j])
print(pascal[N]%(10**9))