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]