Lucas定理解决的是n,m比较大而p是小于100000质数

简而言之就是Lucas(n,m)=C(n%p,m%p)*Lucas(n/p,m/p)%p;

其中组合数C是用任意一种计算10五次方内取模的组合数计算

比如可以预处理阶乘fac[i],然后直接C(n,m)=fac[n]*quickpow(fac[n-m]*fac[m],p-2)%p;

或者O(n)套公式直接算也可以

要注意n可能小于m，因为是取模后的结果，这个时候返回0【不然会RE】

下面给的是预处理阶乘的

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

using namespace std;

const int maxn=1000005,INF=2000000000;

int P;

LL fac[2*maxn],N,M;

void cal(){

	fac[0]=1;

	for(int i=1;i<=P;i++) fac[i]=fac[i-1]*i%P;

}

inline LL qpow(LL a,LL b){

	LL ans=1,base=a%P;

	while(b){

		if(b&1) ans=ans*base%P;

		base=base*base%P;

		b>>=1;

	}

	return ans;

}

inline LL C(LL n,LL m){

	if(n<m) return 0;

	return fac[n]*qpow(fac[n-m]*fac[m]%P,P-2)%P;

}

LL Lucas(LL n,LL m){

	if(n<m||!m) return 1;

	return C(n%P,m%P)*Lucas(n/P,m/P)%P;

}

int main()

{

	int T;

	cin>>T;

	while(T--){

		cin>>N>>M>>P;

		cal();

		cout<<Lucas(N+M,M)<<endl;

	}

	return 0;

}