def comb(n, r):
	res = 1
	for i in range(int(r)):
		res = res * n
		n -= 1
		res = res // (i + 1)
	return res

N = input()
M = input()

N = N // 1e3
N = N % M
print int(comb(M, N) % 1e9)