import Control.Applicative import Text.Printf main = do n <- (read :: String -> Integer) <$> getLine m <- (read :: String -> Integer) <$> getLine print $ choose m (n `div` 1000 * 1000 `mod` (m*1000) `div` 1000) choose n k = (f n k `div` f k k) `mod` 1000000000 where f n k = foldr (*) 1 [n-k+1..n]