program main
  implicit none
  integer*8::N,M,amari
  integer*8,parameter::sen=1000_8
  read *,N,M
  amari = (MOD(N,M*sen)/1000_8)
  print '(i0)',MOD(nCr(M,amari),10**9)
contains
  integer function nCr(N,R)
    integer*8::i,j
    integer*8,intent(in)::N,R
    nCr = 1
    j = N
    do i=1, R
       nCr = (nCr*j)/i
       j   = j - 1
    end do
  end function nCr
end program main