long i;a[10010][10010],m=1e9;main(j){for(**a=1;i++<1e4;)for(j=-1;j++<i;a[i][j]=(a[i-1][j]+a[i-1][j-1])%m);scanf("%ld%d",&i,&j);m=!printf("%d",a[j][i/1000%j]);}