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

N = input()
M = input()

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