program main
  implicit none
  integer*8::N,M,amari
  integer*8,parameter::sen=1000
  read *,N,M
  N = N/sen
  amari = MOD(N, M)
  amari = MIN(amari, M-amari)
  M = get_combination(M,amari)
contains
  function get_combination(N,R) result(NCR)
    implicit none
    !pascal triangle
    integer*8,intent(in)::N,R
    integer*8::NCR,i,j
    integer*4,allocatable::pascal(:,:)
    integer*4,parameter::modulo=10**9
!    print *, N, R
    if(R.eq.0) then
       NCR = 1
    else if(R.eq.1) then
       NCR = N
    else
       allocate(pascal(0:N, 0:N))
       pascal = 0
       pascal(0,0) =1

       do i=1,N
          do j=0,i
             pascal(j,i) = MOD(pascal(j-1,i-1) + pascal(j,i-1),modulo)
          end do
!          print *,i, pascal(:,i)
       end do
       NCR = pascal(R,N)
    end if
    print '(i0)', NCR
  end function get_combination
end program main