n=gets.to_i m=gets.to_i p [*1..m].combination(n/1000-n/1000/m*m).size%1000000000