N = int(input())//1000
M = int(input())
r = N % M
ans = 1
mod = 10 ** 9
inv = 1
seen = [0] * (r + 1)
for i in range(r):
    now = M - i
    for j in range(1, r + 1):
        if seen[j]:
            continue
        if now % j == 0:
            now //= j
            seen[j] = 1
    ans *= now
    ans %= mod
print(ans)