n = input()
m = input()
n /= 1000
n %= m

# mCn
ans = 1
for i in xrange(n):
	ans *= m - i
	ans /= i + 1
ans %= 10 ** 9
print ans