C[10001][10001];
long long N;
i,j,k;
main(M){
	scanf("%lld%d",&N,&M);
	k=N/1000%M;
	for(;i<=M;++i)
		for(C[i][0]=j=1;j<=i;++j)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%1000000000;
	printf("%d\n",C[M][k]);
	return 0;
}