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