P3807 [template] Lucas theorem /lucas theorem

P3807 【 Templates 】 Lucas theorem /Lucas Theorem

$Lucas$ Theorem ： For prime numbers $p$, Yes
$$\left(\genfrac{}{}{0ex}{}{n}{m}\right)\mathrm{m}\mathrm{o}\mathrm{d}p=\left(\genfrac{}{}{0ex}{}{\lfloor n/p\rfloor }{\lfloor m/p\rfloor }\right)\cdot \left(\genfrac{}{}{0ex}{}{n\mathrm{m}\mathrm{o}\mathrm{d}p}{m\mathrm{m}\mathrm{o}\mathrm{d}p}\right)\mathrm{m}\mathrm{o}\mathrm{d}p$$
Equivalent to
$$C(n,m)\%p=C(n/p,m/p)\ast C(n\%p,m\%p)\%p$$
The boundary conditions ： When $m=0$ When , return $1$ .

---

$Code:$

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
typedef long long ll;
using namespace std;

ll qpow(ll a,ll b,ll p){
    // Fast power 
    ll ans=1,base=a;
    while(b){
    
        if(b&1) ans*=base,ans%=p;
        base*=base,base%=p;
        b>>=1;
    }
    return ans;
}

ll C(ll n,ll m,ll p){
    // Combinatorial number 
	if(n<m) return 0;
	if(m>n-m) m=n-m;
	ll a=1,b=1;
	FOR(i,0,m-1){
    
		a=(a*(n-i))%p;
		b=(b*(i+1))%p;
	}
	return a*qpow(b,p-2,p)%p;// Fermat's small Theorem 
}

ll Lucas(ll n,ll m,ll p){
    // Lucas theorem 
	if(m==0) return 1;
	return Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}

int main(){
    
	int T;cin>>T;
	while(T--){
    
		ll n,m,p;
		cin>>n>>m>>p;
		cout<<Lucas(n+m,m,p)%p<<endl;
	}
	return 0;
}