program main
  implicit none
  integer*8::N,M,amari
  integer*4,parameter::sen=1000
  integer*4::memo(10**4,0:10**4)
  data memo/100010000*0/

  read *,N,M
  N = N/sen
  amari = MOD(N, M)
  memo = 0
  print '(i0)', get_combination(M, MIN(amari, M-amari), memo)
contains
  recursive function get_combination(N,R, memo) result(NCR)
    integer*8::N,R,NCR
    integer*4,parameter::modular=10**9
    integer*4::memo(10**4,0:10**4)
    if(memo(N,R).ne.0) then
       NCR = memo(N,R)
    else
       if(R.eq.0) then
          NCR = 1
       else if(R.eq.1) then
          NCR = N
       else if(N-R.lt.R) then
          NCR = get_combination(N, N-R, memo)
       else
          NCR = get_combination(N-1,R,memo) + get_combination(N-1,R-1,memo)
       end if
       NCR = MOD(NCR, modular)
       memo(N,R) = NCR
    end if
   end function get_combination
 end program main