combination :: Integer -> Integer -> Integer
combination n k = (product [n-k+1..n]) `div` (product [1..k])

main = do
	[n, m] <- getContents >>= return . map read . lines
	let k = n `mod` (m * 1000) `div` 1000
	print $ combination m (minimum[k,m-k]) `mod` (10^9)