题意：求C(m,n)的后9位，不要前缀0，范围10^6

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll pw(ll a,ll b,ll nn){
    ll t=1,y=a;
    while(b){
        if(b&1) t=t*y%nn;
        y=y*y%nn;
        b>>=1;
    }
    return t;
}
ll cnt(ll nnn,int i){
	ll c=0;
	int nnnn=nnn; 
	while(nnnn){
		nnnn/=i,c+=nnnn;
	}
	return c;
}
int main(){
	ios::sync_with_stdio(false);
	ll m,n,a=1,mod=1000000000;
	cin>>m>>n;
	if(m<n)cout<<"0\n",exit(0);
	if(n==m||n==1)cout<<m<<"\n",exit(0);
	bool p[m+1]={0};
	memset(p,0,sizeof(p));
	for(int i=2;i<m;i++){
		if(!p[i]){
			ll c=cnt(m,i)-cnt(n,i)-cnt(m-n,i);
			a=(a*pw(i,c,mod))%mod;
			for(ll j=(ll)(i*i);j<=m;j+=i){
				p[i]=1;
			}
		}
	}
	cout<<a;
	return 0;
}