def fact(x):
    if x == 0:
        return 1
    else:
        return x * fact(x - 1)

def comb(r, c):
    return fact(r) / fact(r-c) / fact(c)

N = input()
M = input()
N /= 1000
N %= M
print(comb(M, N) % 1000000000)