def nck(n, k):
    x = 1
    for i in range(k):
        x = x * (n - i) // (i + 1)
        x %= MOD
    return x


MOD = 10**9
N = int(input())
M = int(input())

m = (N % (M * 1000)) // 1000
ans = nck(M, m)
print(ans)