把n写成p进制a[n]a[n-1][n-2]…a[0],把m写成p进制b[n]b[n-1][n-2]…b[0],则C(n,m)与C(a[n],b[n])*C(a[n-1],b[n-1])*C(a[n-2],b[n-2])*…*C(a[0],b[0])模p同余
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define int long long
int t,n,m,p;
int qpow(int x,int k){
int s=;
while(k){
if(k&) s=s*x%p;
k>>=;
x=x*x%p;
}
return s;
}
int C(int n,int m){ //组合数公式
if(n<m) return ;
if(m>n-m) m=n-m;
int s1=,s2=;
for(int i=;i<m;i++){
s1=s1*(n-i)%p;
s2=s2*(i+)%p;
}
return s1*qpow(s2,p-)%p; //快速幂求逆元
}
int lucas(int n,int m){
if(m==) return ;
return C(n%p,m%p)*lucas(n/p,m/p)%p; //卢卡斯定理
}
#undef int
int main()
#define int long long
{
scanf("%lld",&t);
while(t--){
scanf("%lld%lld%lld",&n,&m,&p);
printf("%lld\n",lucas(n+m,m));
}
return ;
}