浙江常升建设有限公司网站/腾讯广告代理商加盟

对于组合数，往往要用到阶乘，但是阶乘的数据极其之大，所以要用取模的办法防止数据溢出。

而卢卡斯定理在这个时候就有很大的用处了，来看百度百科上的简介。

代码如下 Luogu P3807

#include<bits/stdc++.h>
using namespace std;
int T; 
int n,m,p;
long long ksm(long long a,long long b,long long p){long long base=1;while(b){if(b&1) base=base*a%p;a=a*a%p;b>>=1;}return base;
}
long long C(long long n,long long m){if(m>n) return 0;long long a=1,b=1;for(long long i=n-m+1;i<=n;i++){a=a*i%p;}for(long long i=1;i<=m;i++){b=b*i%p;}return a*ksm(b,p-2,p)%p;
}
long long Lucas(long long n,long long m){if(!m) return 1;else return (C(n%p,m%p)*Lucas(n/p,m/p))%p;
}
int main(){scanf("%d",&T);for(int i=1;i<=T;i++){scanf("%d%d%d",&n,&m,&p);printf("%lld\n",Lucas(n+m,m));}return 0;
}