组合数学推推推最后，推得要求C（n+m，m）%p
其中n，m小于10^9,p小于1^5
用Lucas定理求（Lucas定理求nm较大时的组合数）
因为p数据较小可以直接阶乘打表求逆元
求逆元时，由费马小定理知道p为素数时，a^p-1=1modp可以写成a*a^p-2=1modp
所以a的逆元就是a^p-2,
可以求组合数C（n，m）%p中除法取模,将其转化为乘法取模
即 n!/(m!*(n-m)!)=n!*(m!*(n-m)!)^p-2
求C（n+m，m）。
n，m<=1000，二维数组递推。
n，m<=1000000，一维数组预处理出阶乘。
Lucas适用于n，m较大，MOD较小的情况。
#include <iostream>
#define MAX 100005 typedef long long ll;
using namespace std; ll mul[MAX],MOD; void init(){
mul[]=;
for(int i=;i<=MOD;i++){
mul[i]=mul[i-]*i%MOD;
}
}
ll qMod(ll a,ll b){
ll ans=;
a%=MOD;
while(b){
if(b&) ans=ans*a%MOD;
b>>=;
a=a*a%MOD;
}
return ans;
}
ll C(ll a,ll b){
if(a<b) return ;
return mul[a]*qMod(mul[b]*mul[a-b],MOD-)%MOD;
}
ll Lucas(ll a,ll b){
if(b==) return ;
return (C(a%MOD,b%MOD)*Lucas(a/MOD,b/MOD))%MOD;
}
int main()
{
int T;
ll n,m;
cin>>T;
while(T--){
cin>>n>>m>>MOD;
init();
cout<<Lucas(n+m,m)<<endl;
}
return ;
}