大非质数取模算组合数板子-526互联

const int N=1e5+10,M=13;
int n,mod,l,r;
ll ans,p[M],br[M],phi;
inline ll ksm(ll a,ll b){
	ll d=1;
	while(b){
		if(b&1) d=d*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return d;
}
namespace big_mod{
	struct num{
		ll x,r[M];
	}fac[N],I,B;
	inline num operator*(num a,num b){
		num c=I;
		for(int i=1;i<=p[0];++i) c.r[i]=a.r[i]+b.r[i];
		c.x=a.x*b.x%mod;
		return c;
	}
	inline num operator/(num a,num b){
		num c;
		for(int i=1;i<=p[0];++i) c.r[i]=a.r[i]-b.r[i];
		c.x=a.x*ksm(b.x,phi-1)%mod;
		return c;
	}
	inline num cng(ll y){
		num c=I;
		for(int i=1;i<=p[0]&&y;++i){
			while(y%p[i]==0) ++c.r[i],y/=p[i];
		}
		c.x=y;
		return c;
	}
	inline ll rec(num a){
		ll y=a.x;
		for(int i=1;i<=p[0];++i){
			y=y*ksm(p[i],a.r[i])%mod;
		}
		return y;
	}
	inline void init(){
		ll x=mod;
		phi=mod;
		for(ll i=2;i*i<=x;++i){
			if(x%i==0){
				phi=phi/i*(i-1);
				p[++p[0]]=i;
				while(x%i==0) ++br[p[0]],x/=i;
			}
		}
		if(x>1) p[++p[0]]=x,br[p[0]]=1,phi=phi/x*(x-1);
		I.x=1;
		B.x=0;
		for(int i=1;i<=p[0];++i) I.r[i]=0;
		fac[0]=I;
		for(ll i=1;i<=n;++i) fac[i]=fac[i-1]*cng(i);
	}
	inline num C(int n,int m){
		if(m<0||(m>>=1)>n) return B;
		return (fac[n]/fac[m])/fac[n-m];
	}
}