import Data.Tuple
import Data.List

data Tree a = Node a (Tree a) (Tree a)
memoize f = memof where memof = f (query (blank memof))
blank f = blank' 1 where blank' k = Node (f k) (blank' (2*k)) (blank' (2*k+1))

query m x = query' m bits
 where
  bits = tail (reverse (take w (unfoldr (return . swap . flip divMod 2) x)))
  w = floor (logBase 2 (fromIntegral x)) + 1
  query' (Node v left right) bs
   | bs == [] = v
   | head bs == 0 = query' left (tail bs)
   | otherwise = query' right (tail bs)

q = 10^9

comb n r = div (fact n) (fact r * fact (n-r))
fact = memoize (\f x -> if x<=1 then 1 else x * f (x-1))

main = getContents >>= print . otoshidama . map read . words

otoshidama :: [Integer] -> Integer
otoshidama [n,m] = let r = mod n (1000*m) in mod (comb m (div r 1000)) q