def perm(n, k):
    res = 1
    i = 0
    while i < k:
        res *= n - i
        res //= i + 1
        i += 1
    return res


N = int(input())
M = int(input())

K = (N // 1000) % M
print(perm(M, K) % 10 ** 9)