def combi(n,m)
	a = b = 1
	for i in 1..m
		a *= i
		b *= i+n-m
	end
	return b/a
end

n = gets.to_i
m = gets.to_i

amari = (n - n/1000/m*1000*m)/1000
p combi(m,amari)%1000000000