def combi(n,k)
  r=1
  n.downto(k){|e|
    r=r*e/(n-e+1)
  }
  r
end
n = gets.to_i
m = gets.to_i

k = (n%(m*1000))/1000

p combi(m,k)%1000000000