#include<iostream>
using namespace std;
long n,m;
main()
{
	cin>>n>>m;n-=n/(m*1000)*m*1000;n/=1000;
	long ans=1;
	for(long i=1;i<=n;i++)
	{
		ans=ans*(m-i+1)/i;
	}
	cout<<ans%int(1e9)<<endl;
}