#include <iostream>
using namespace std;
typedef long long ll;
const int mod=1e9;
int main(){
  ll N,M;
  cin>>N;
  cin>>M;
  ll D=N%(1000*M);
  D/=1e3;
  if(D==0){
    cout<<1<<endl;
  } else {
  ll E=1;
  for(int i=M; i>M-D; --i){
    E%=mod;
    i%=mod;
    E*=i;
  }
  ll F=1;
  for(int i=D; i>=1; --i){
    F%=mod;
    i%=mod;
    F*=i;
  }
  E%=mod;
  F%=mod;
  ll G=E/F;
  G%=mod;
  cout<<G<<endl;
  }
  return 0;
}