MOD=10**9
N = int(input())
M = int(input())
N = (N//1000)%M
pascal = [[0 for j in range(10000+1)]for i in range(10000+1)]
for i in range(10000):
	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)