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

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

p combi(m,k)%1000000000