def count_p_factorial(n, p):
    res = 0
    while n > 0:
        n = n // p
        res += n
    return res

def main():
    import sys
    N, M = map(int, sys.stdin.read().split())
    total = M * 1000
    X = N // total
    R = N - X * total
    K = R // 1000

    if K == 0:
        print(1)
        return

    MOD = 10**9

    # Sieve of Eratosthenes to find all primes up to M
    sieve = [True] * (M + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(M**0.5) + 1):
        if sieve[i]:
            sieve[i*i::i] = [False] * len(sieve[i*i::i])
    primes = [i for i, is_p in enumerate(sieve) if is_p]

    result = 1
    for p in primes:
        # Numerator: count_p(M! / (M-K)!)
        cnt_numerator = count_p_factorial(M, p) - count_p_factorial(M - K, p)
        # Denominator: count_p(K!)
        cnt_denominator = count_p_factorial(K, p)
        exponent = cnt_numerator - cnt_denominator
        if exponent > 0:
            result = (result * pow(p, exponent, MOD)) % MOD
    print(result)

if __name__ == "__main__":
    main()