MOD = 1000000000

n = gets.to_i
m = gets.to_i

n -= ((n/m)/1000) * 1000 * m

n /= 1000


ans = 1
for i in 0...n do
	ans *= m-i
end

for i in 0...n do
	ans /= n-i
end

puts ans%MOD