from math import factorial
def ncr(n, r):
    if n < r or r < 0:
        return 0
    return factorial(n) // (factorial(n-r) * factorial(r))

mod = 10**9
N = int(input())
M = int(input())
N = (N % (1000 * M)) // 1000
print(ncr(M, N) % mod)