def C(n, r): return fact[n] // fact[r] // fact[n-r] fact = [1] for i in range(1, 10001): fact.append(fact[-1] * i) N = int(input()) M = int(input()) MOD = 10 ** 9 i = N // (M * 1000) c = (N - M * 1000 * i) // 1000 ans = C(M, c) % MOD print(ans)