题目很简单，很暴力，就是组合数，没有其他的。
但是直接暴力会炸wow
我们可以利用Lucas定理来分解字问题。
Lucas定理：C（n,m）(mod p)=C(n%p,m%p)*C(n/p,m/p)(mod p);
所以，我们可以把这个题目分解成子问题：
C(n,m+n)(mod p)=C(n%p,m+n%p)*C(n/p,(m+n)/p);
而第二个C又可以用Lucas定理求，
所以可以递归求解了
当m=0时，Lucas返回1（C（n,0）=1）
但是，还是要注意：
这题要逆元！！！
这题要逆元！！！
这题要逆元！！！
因为组合要除法，所以需要逆元。
还好题目亲切，p一定是质数，所以直接费马小搞定了。
于是：O（n）处理阶乘，logn处理逆元（卡速米）lognLucas
所以整体复杂度应该是O（Tnlog^2n ）（应该不太对）
贴代码，有些注意事项在代码里写出来
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+;
long long n,m,p;
long long ksm(long long a,long long b)
{
a%=p;
long long res=;
while(b)
{
if(b%==)
res=(res*a)%p;
a=(a*a)%p;
b>>=;
}
return res;
}
long long fac[maxn];
long long C(long long a,long long b)
{
if(a<b)//坑点，如果总数小于方案数（C（n,m）n<m,也就是选不出来）要跳出
return ;
return (fac[a]*ksm(fac[b],p-))%p*ksm(fac[a-b],p-)%p;//逆元乘法，求组合数
}long long lucas(long long a,long long b)
{
if(b==)
return ;
return lucas(a/p,b/p)*C(a%p,b%p)%p;//Lucas表达
}int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld%lld",&n,&m,&p);
fac[]=;//阶乘
for(long long i=;i<=p;i++)
{
fac[i]=(fac[i-]*i)%p;//阶乘
}
printf("%lld\n",lucas(n+m,n));//跑Lucas
}
return ;
}
（完）
