program main
  implicit none
  integer*8::N,M,amari
  integer*8,parameter::sen=1000
  read *,N,M
  N = N/sen
  amari = MOD(N, M)
  print '(i0)', get_combination(M, MIN(amari, M-amari))
contains
  recursive function get_combination(N,R) result(NCR)
    integer*8::N,R,NCR
    integer*8,parameter::modular=10**9
    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)
    else
       NCR = get_combination(N-1,R) + get_combination(N-1,R-1)
    end if
    NCR = MOD(NCR, modular)
  end function get_combination
end program main