main = getContents >>= print . solve . map read . lines

solve :: [Integer] -> Integer
solve [n, m] = c m l `mod` 1000000000
    where
        l = mod n (m * 1000) `div` 1000
        c a b = product [(a - b + 1)..a] `div` product [2..b]