### 扩展欧几里得
```cpp
int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1;
y=0;
return a;
}
int r=exgcd(b,a%b,x,y);
int p=y;
y=x-(a/b*y);
x=p;
return r;
}
```
------------
### 中国剩余定理
```cpp
const int maxn=15;
struct CRT{
int id;
int a[maxn],m[maxn];
long long lcm;
CRT(){lcm=1;}
void insert(int ai,int mi){
a[++id]=ai;
m[id]=mi;
lcm*=mi;
}
long long exgcd(long long a,long long b,long long &x,long long &y){
if(b==0){
x=1;
y=0;
return a;
}
long long r=exgcd(b,a%b,x,y);
long long p=y;
y=x-(a/b*y);
x=p;
return r;
}
long long qtime(long long a,long long b,long long P){
long long res=0;
while(b){
if(b&1)res=(res+a)%P;
b>>=1;
a=(a+a)%P;
}
return res;
}
long long solve(){
long long res=0;
for(int i=1;i<=id;i++){
long long x,y;
exgcd(lcm/m[i],m[i],x,y);
while(x<0)x+=m[i];
long long tmp=qtime(lcm/m[i],qtime(x,a[i],lcm),lcm);
res=(res+tmp)%lcm;
}
return res;
}
}crt;
```
### lucas定理
```cpp
#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1e5+100;
int n,m,P;
long long qpow(long long p,long long q){
long long res=1;
while(q){
if(q&1)res=res*p%P;
p=p*p%P;
q>>=1;
}
return res;
}
long long f[maxn],fr[maxn];
void init(){
f[0]=fr[0]=1;
for(int i=1;i<=P;i++)
f[i]=f[i-1]*i%P;
fr[P-1]=qpow(f[P-1],P-2);
for(int i=P-2;i>=1;i--)
fr[i]=fr[i+1]*(i+1)%P;
}
long long C(int a,int b){
if(a<b)return 0;
return f[a]*fr[b]%P*fr[a-b]%P;
}
long long lucas(int a,int b){
if(b==0)return 1;
return lucas(a/P,b/P)*C(a%P,b%P)%P;
}
int main(){
for(int _=(cin>>_,_);_--;){
cin>>n>>m>>P;
init();
cout<<lucas(n+m,m)<<endl;
}
return 0;
}
```