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

assert 1 <= N <= 10 ** 16
assert 1 <= M <= 10 ** 4
#多倍長解

def C(N, K):
    result = 1
    for i in xrange(1, K + 1):
        result *= (N - i + 1)
        result /= i
    return result


A = (N // 1000) / M
K = (N // 1000) - A * M

ans = C(M, K)%1000000000

print ans