当$p$为素数时

　　$$C_n^m\equiv C_{n/p}^{m/p}*C_{n\%p}^{m\%p}(mod\ p)$$

　　设$n=s*p+q,m\equiv t*p+r(q,r<=p)$

　　我们要证$C_{s*p+q}^{t*p+r}\equiv C_s^t*C_q^r$

　　首先得有个前置知识，费马小定理$x^p\equiv x(mod\ p)$

　　那么$(x+1)^p\equiv x+1(mod\ p)$

　　且$x^p+1\equiv x+1(mod\ p)$

　　所以$(x+1)^p\equiv x^p+1$

　　然后$(x+1)^n\equiv (x+1)^{s*p+q}$

　　$\equiv ((x+1)^p)^s*(x+1)^q$

　　$\equiv (x^p+1)^s*(x+1)^q$

　　然后用二项式定理展开

　　$\equiv \sum _{i=0}^s C_s^i*x^{i*p}*\sum_{j=0}^qC_q^j*x^j$

　　总之就是$(x+1)^p\equiv \sum _{i=0}^s C_s^i*x^{i*p}*\sum_{j=0}^qC_q^j*x^j$

　　然后考虑把两边的多项式展开一下

　　那么两边肯定都有$x^m$即$x^{t*p+r}$这一项（这是最上面的假设）

　　左边的$x^m$的系数，根据上面的性质4推出来，应该是$C_n^m$

　　然后右边嘞？只有$i=t,j=r$的时候才会有这一项，所以这一项的系数就是$C_s^t*C_q^r$

　　然后又因为$s=n/p,t=n\%p,q=m/p,r=m\%p$

　　然后就能证明$C_n^m\equiv C_{n/p}^{m/p}*C_{n\%p}^{m\%p}(mod\ p)$

　　然而万一$q<r$该怎么办？那样的话$j$根本不可能等于$r$啊？

　　所以那样的话答案就是$0$

　　因为上面乘上$C_{n\%p}^{m\%p}$答案就是$0$

　　如何证明？

　　我们设$f=n-m=z*p+x$

　　因为$r>t,x+r\equiv t(mod\ p)$

　　所以$x+r=p+t$

　　又因为$z*p+x+q*p+r=s*p+t$

　　所以$z+q=s-1$

　　那么带进通项公式$C_n^m=\frac {n!}{m!*f!}$之后，分子中有$s$个$p$的倍数（不考虑有$p^2$之类的，因为下面有的话上面肯定也有），分母中有$s-1$个$p$的倍数，抵消之后分子中还有一个$p$，那么这个数就是$p$的倍数，模$p$肯定余$0$啦

　　累死我了……

1 // luogu-judger-enable-o2 2 //minamoto 3 #include
     
       4 #include
      
        5 #define ll long long 6 using namespace std; 7 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 8 char buf[1<<21],*p1=buf,*p2=buf; 9 inline ll read(){10     #define num ch-'0'11     char ch;bool flag=0;ll res;12     while(!isdigit(ch=getc()))13     (ch=='-')&&(flag=true);14     for(res=num;isdigit(ch=getc());res=res*10+num);15     (flag)&&(res=-res);16     #undef num17     return res;18 }19 const int N=100005;20 ll n,m,p;21 ll fac[N],inv[N];22 void init(){23     fac[0]=1;24     for(int i=1;i<=p;++i)25     fac[i]=fac[i-1]*i%p;26 }27 ll qpow(ll a,ll b){28     ll res=1;29     while(b){30         if(b&1) res=res*a%p;31         b>>=1,a=a*a%p;32     }33     return res;34 }35 ll C(ll n,ll m){36     if(m>n) return 0;37     return fac[n]*qpow(fac[m]*fac[n-m],p-2)%p;38 }39 ll Lucas(ll n,ll m){40     if(m==0) return 1;41     return Lucas(n/p,m/p)*C(n%p,m%p)%p;42 }43 int main(){44     int T=read();45     while(T--){46         n=read(),m=read(),p=read();47         init();48         printf("%lld\n",Lucas(m+n,m));49     }50     return 0;51 }