N = gets.to_i
M = gets.to_i
k = (N % (M * 1000)) / 1000
def f(n)
  if n == 0
    1
  else
    (1..n).inject(:*)
  end
end
ans = (f(M) / (f(M - k) * f(k))) % (10**9)
puts ans