n = int(input())
m = int(input())

n //= 1000
r = n % m
ans = 1
for i in range(r):
    ans *= m - i
for i in range(r):
    ans //= i + 1
ans %= 10**9
print(ans)