#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define E 1000000000
int main(){
	ll n,m;	cin>>n>>m;
	n/=1000;
	n%=m;
	//mCnを求めれば良い
	ll ans=1;
	if(n>m/2)	n=m-n;
	for(int i=0;i<n;i++){
		ans=(ans*(m-i)/(n-i))%E;
	}
	cout<<ans<<endl;
	return 0;
}