def perm(N, K):
    i = 0
    ret = 1
    while i < K:
        ret *= N - i
        ret /= i + 1
        i = i + 1
    return ret


N = int(raw_input())
M = int(raw_input())

N /= 1000
N %= M

print(perm(M, N) % 1000000000)