#include<stdio.h>
#include<stdlib.h>

void run(void){
  long long int n;
  int m;
  scanf("%lld%d",&n,&m);
  int t=(int)(n%(1000*m))/1000;

  int *comb=(int *)calloc((m+1)*(m+1),sizeof(int));
  comb[0]=1;
  const int mod=1000000000;
  int i,j;
  for(i=1;i<=m;i++){
    comb[i*(m+1)]=1;
    for(j=1;j<=i;j++){
      comb[i*(m+1)+j]=(comb[(i-1)*(m+1)+j-1]+comb[(i-1)*(m+1)+j])%mod;
    }
  }
  printf("%d\n",comb[m*(m+1)+t]);
  return;
}

int main(void){
  run();
  return 0;
}