n = gets.to_i
m = gets.to_i
d1 = (n / m) / 1000 * 1000
d2 = n - d1 * m
c = d2 / 1000
q1 = 1
q2 = 1
c.times do |x|
    q1 *= (x + 1)
    q2 *= m - x
end
puts (q2 / q1) % 1000000000