func main()
	var N: int :: cui@input().toInt(&)
	var M: int :: cui@input().toInt(&)
	var num: int :: (N / 1000) % M
	var ans: int :: 1
	var mul: []int :: #[num]int
	for i(0, num - 1)
		do mul[i] :: M - i
	end for
	for div(1, num)
		for i(0, num - 1)
			if(mul[i] % div = 0)
				do mul[i] :/ div
				break i
			end if
		end for
	end for
	for i(0, num - 1)
		do ans :* mul[i]
		do ans :% 10 ^ 9
	end for
	do cui@print("\{ans}\n")
end func