#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long int ll;
const ll E=1e9;
ll dp[10001][10001];
int main(){
	ll n,m;	scanf("%lld %lld",&n,&m);
	n/=1000;
	n%=m;
	//mCnを求める
	dp[0][0]=1;
	for(int i=1;i<=10000;i++){
		dp[i][0]=1;	dp[i][i]=1;
		for(int j=1;j<=i;j++){
			dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%E;
		}
	}
	if(dp[m][n]==0)	dp[m][n]++;
	printf("%lld\n",dp[m][n]);
	return 0;
}