给定n,m,p(1≤n,m,p≤1051\le n,m,p\le 10^51≤n,m,p≤105)

求 Cn+mm mod pC_{n+m}^{m}\ mod\ pCn+mm​ mod p

保证P为prime

C表示组合数。

一个测试点内包含多组数据。

输入输出格式

输入格式：

第一行一个整数T(T≤10T\le 10T≤10)，表示数据组数

第二行开始共T行，每行三个数n m p，意义如上

输出格式：

共T行，每行一个整数表示答案。

输入输出样例

输入样例#1：

21 2 52 1 5

输出样例#1：

33

思路

卢卡斯定理；

C(m,n)%p=C(m/p,n/p)*C(m%p,n%p)%p;

代码

1 #include
     
       2 const int maxn=1e5+10; 3 int T,n,m,p; 4 int f[maxn]={
   1}; 5 void init(){
   for(int i=1;i<=p;i++) f[i]=(1ll*f[i-1]*i)%p;} 6 int FP(int x,int y){ 7     int ret=1; 8     while(y){ 9         if(y&1) ret=(1ll*ret*x)%p;10         y>>=1,x=(1ll*x*x)%p;11     }12     return ret;13 }14 int IE(int x){
   return FP(x,p-2);}15 int C(int m,int n){16     if(m>n) return 0;17     return 1ll*f[n]*IE(f[n-m])%p*IE(f[m])%p;18 }19 int Lucas(int m,int n){20     if(!m) return 1;21     return 1ll*Lucas(m/p,n/p)*C(m%p,n%p)%p;22 }23 int main(){24     scanf("%d",&T);25     while(T--){26         scanf("%d%d%d",&n,&m,&p);27         init();28         printf("%d\n",Lucas(m,n+m)%p);29     }30     return 0;31 }