前置芝士
二项式定理（
秦九韶算法（
定义
设 (P) 为素数，(a, b in N^*) ,并且
[a = a_kp^k + a_{k - 1}p^{k-1} + dots + a_1p+ a_0 \ b = b_kp^k + b_{k-1}p^{k-1} + cdots + b_1p + b_0
]
这里 (0 leq a_i, b_i leq p - 1) 都是整数，(i = 0,1,2, cdots, k.) 则有
[C_a^b equiv C_{a_k}^{b_k} * C_{a_{k-1}}^{b_{k-1}} * cdots * C_{a_0}^{b_0} (mod P)
]
证明
设 (f(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_0,g(x)=b_nx^n+b_{n-1}x^{n-1}+...+b_0) 是两个整系数多项式，如果对 (0leq ileq n) ，都有 (a_iequiv b_i~(mod~m)) ，那么称 (f(x)) 与 (g(x)) 对模 (m) 同余，记作 (f(x)equiv g(x)~(mod~m))
由于 (p) 为素数，可知对 (1leq jleq p-1) ，都有 (C_p^j=frac pjC_{p-1}^{j-1}equiv 0~(mod~p)) 。
于是：
[egin{aligned}(1+x)^p&=1+C_p^1x+...+C_p^{p-1}x^{p-1}+x^p\&equiv 1+x^p~(mod~p)end{aligned}
]
利用上述结果，可知：
[egin{aligned}(1+x)^a&=(1+x)^{a_0}((1+x)^p)^{a_1}~~cdot~...~cdot~~((1+x)^{p^k})^{a_k}\&equiv(1+x)^{a_0}(1+x^p)^{a_1}~~cdot~...~cdot~~(1+x^{p^k})^{a^k}~(mod~p)end{aligned}
]
对比两边 (x^b(1leq bleq a)) 项的系(想不明白用二项式定理)，可得：
[C_a^bequiv C_{a_k}^{b_k}cdot C_{a_{k-1}}^{b_{k-1}}cdot...cdot C_{a_0}^{b_0}~(mod~p)
]
或：
[C_a^bequiv prodlimits_{i=0}^kC_{a_i}^{b_i}~(mod~p)
]
证毕
作用
这个定理的意义就在于把 (a) 或者 (b) 或者两者均大于 (p) 的组合数 (C_a^b) 转换为求解小于 (p) 的整数 (a_k) 和 (b_k) 的组合数 (C^{b_k}_{a_k}) 的乘积。
而对于 (a_0,a_1,...,a_k) 可以通过秦九韶算法：
[a=(((...(0*p+a_k)...)*p+a_2)*p+a_1)*p+a_0
]
逆向得到，即
[a_0=(a/p^0)\%p\a_1=(a/p^1)\%p\a_2=(a/p^2)\%p\vdots \a_k=(a/p^k)\%p
]
显然，秦九韶的逆向算法也同样适用于求解 (b) 。
（现在，通过pascal打表的方法在 (O(1)) 的时间里求得小范围的组合数，用逆元的方法可以求取模数范围内的组合数，在加上Lucas定理，就可以求取任意范围内的组合数了。）
代码
#include<bits/stdc++.h>
#define N 100010
using namespace std;
typedef long long ll;
ll a[N];
int p;
ll pow(ll y,int z,int p){
y%=p;ll ans=1;
for(int i=z;i;i>>=1,y=y*y%p)if(i&1)ans=ans*y%p;
return ans;
}
ll C(ll n,ll m){
if(m>n)return 0;
return ((a[n]*pow(a[m],p-2,p))%p*pow(a[n-m],p-2,p)%p);
}
ll Lucas(ll n,ll m){
if(!m)return 1;
return C(n%p,m%p)*Lucas(n/p,m/p)%p;
}
inline int read(){
int f=1,x=0;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
return f*x;
}
int main(){
int T=read();
while(T--){
int n=read(),m=read();p=read();
a[0]=1;
for(int i=1;i<=p;i++)a[i]=(a[i-1]*i)%p;
cout<<Lucas(n+m,n)<<endl;
}
}