import Control.Applicative ((<$>), (<*>))

combi :: Integral a => a -> a -> a
combi n m = div (product [n, n - 1 .. n - m + 1]) $ product [1 .. m]

calc :: Integer -> Integer -> Integer
calc n m = combi m r `mod` 1000000000
    where r = div n 1000 `mod` m

main :: IO ()
main = (calc <$> readLn) <*> readLn >>= print