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