逆元与组合数

int add(int a,int b)
{
	int c=(a+b);
	if (c>=mod) c-=mod;
	return c;
}
int mul(int a,int b)
{
	ll c=1ll*a*b;
	return c-c/mod*mod;
}
int fpow(int x,int power)
{
	int ans=1;
	while (power)
	{
		if (power&1) ans=mul(ans,x);
		power>>=1;
		x=mul(x,x);	
	} 
	return ans;
}
int fac[maxn];
int inv[maxn];
int facinv[maxn];
void fac_init()//load fac, inv, facinv
{
    fac[0]=fac[1]=1;
    for (int i=1;i<=MAX;i++) fac[i]=mul(fac[i-1],i);
    inv[0]=inv[1]=1;    
    for(int i=2;i<=MAX;i++) inv[i]=mul(mod-mod/i,inv[mod%i]);    
	facinv[0]=facinv[1]=1;
	for(int i=2;i<=MAX;i++) facinv[i]=inv[i];    
    for(int i=2;i<=MAX;i++) facinv[i]=mul(facinv[i],facinv[i-1]);
}	
int C(int i,int j)
{
	if (i<j) return 0;
	if (i<0||j<0) return 0;
	return mul(fac[i],mul(facinv[i-j],facinv[j]));
//	return mul(mul(fac[i],fpow(fac[i-j],mod-2)),mul(tmp,fpow(fac[j],mod-2)));
}