n = gets.to_i
m = gets.to_i
n = n / 1000 % m
n = [n, m-n].min
ans = 1
(m-n+1..m).each do |i|
  ans *= i
end
(1..n).each do |i|
  ans /= i
end
p ans % 1000000000