{-# LANGUAGE BangPatterns #-}

import Control.Monad
import Control.Monad.Fix
import Data.IORef

perm :: Integer -> Integer -> IO Integer
perm n k = do
  ret <- newIORef (1 :: Integer)
  flip fix (0 :: Integer) $ \loop !j -> do
    if j < k then do
      modifyIORef' ret ((`div` (j + 1)) . (* (n - j)))
      loop (j + 1)
    else readIORef ret

main :: IO ()
main = do
  n <- readLn :: IO Integer
  m <- readLn :: IO Integer
  let n' = (n `div` 1000) `mod` m
  print . flip mod 1000000000 =<< perm m n'