这篇题解写的思路是很简单，但是有一些误导性严重的笔误，大量冗余语言，排版也不是很规范，修正并略微去繁从简如下：

如何不用Lucas

这个模板的 $n,m$ 都是 $10^5$，显然不用 Lucas 也可以做。

注：Lucas复杂度 $O(p\log n)$，接近于 $O(p)$，暴力做复杂度是 $O(n)$

然后直接用逆元求 $\dfrac{(n+m)!}{n! \times m!}$，可以直接把上下的 $n!$ 约去，变为 $\dfrac{A^{n+1}_{n+m}}{A^m_m}$。

分子边乘边取模即可，分母可以把每个因数不断除以 $p$ 直到与 $p$ 互质，然后需要判断分子分母出现的因数 $p$ 的个数是否相同。相同直接输出逆元，不相同输出 $0$ 即可。

代码（费马小定理）

#include<iostream>
#include<cstdio>
#define ni(x) power(x,md-2)
using namespace std;

char rc;
void read(long long &x)
{
    x=0;rc=getchar();
    while(rc<'0'||rc>'9')
      rc=getchar();
    while(rc>='0'&&rc<='9')
      x=x*10+rc-'0',rc=getchar();
}

long long n,m,md,t,T,i,ans;//md就是题目的p 

long long power(long long a,long long n)
{
    long long ans=1;
    while(n)
    {
        if(n&1)
          ans=(ans*a)%md;
        a=(a*a)%md;
        n>>=1;
    }
    return ans;
}

int cnt;
long long check(long long x,long long detla)//除掉因子p 
{
    while(x%md==0)
      x/=md,cnt+=detla;//算分子的时候detle每次+1，分母每次-1 
    return x;
}

int main()
{
    cin>>t;
    for(T=1;T<=t;T++)
    {
        cin>>n>>m>>md;cnt=0;
        ans=1;
        for(i=n+1;i<=n+m;i++)
          ans=(ans*check(i,1))%md;
        for(i=2;i<=m;i++)
          ans=(ans*ni(check(i,-1)))%md;
        cout<<(cnt==0?ans:0)<<endl;
    }
    return 0;
}

代码（线性筛）

#include<iostream>
#include<cstdio>
using namespace std;

char rc;
void read(long long &x)
{
    x=0;rc=getchar();
    while(rc<'0'||rc>'9')
      rc=getchar();
    while(rc>='0'&&rc<='9')
      x=x*10+rc-'0',rc=getchar();
}

long long n,m,md,t,T,i,ans,ni[200005];//md就是题目中的p 

int cnt;
long long check(long long x,long long detla)//除掉因子p 
{
    while(x%md==0)
      x/=md,cnt+=detla;//算分子的时候detle每次+1,分母每次-1 
    return x;
}

int main()
{
    cin>>t;
    for(T=1;T<=t;T++)
    {
        cin>>n>>m>>md;cnt=0;
        ni[1]=1;//这三行是线性筛逆元 
        for(i=2;i<md;i++)
          ni[i]=((-(md/i)*ni[md%i])%md+md)%md;//注意要 求正数 
        ans=1;
        for(i=n+1;i<=n+m;i++)
          ans=(ans*check(i,1))%md;
        for(i=2;i<=m;i++)
          ans=(ans*ni[check(i,-1)%md])%md;//线性筛逆元只能筛到p-1，大于p的m逆元等于m%p的逆元 
        cout<<(cnt==0?ans:0)<<endl;
    }
    return 0;
}

## 如何不用Lucas

这个模板的 $n,m$ 都是 $10^5$，显然不用 Lucas 也可以做。

注：Lucas复杂度 $O(p\log n)$，接近于 $O(p)$，暴力做复杂度是 $O(n)$

然后直接用逆元求 $\dfrac{(n+m)!}{n! \times m!} $，可以直接把上下的 $n!$ 约去，变为 $\dfrac{A^{n+1}_{n+m}}{A^m_m}$。

分子边乘边取模即可，分母可以把每个因数不断除以 $p$ 直到与 $p$ 互质，然后需要判断分子分母出现的因数 $p$ 的个数是否相同。相同直接输出逆元，不相同输出 $0$ 即可。

代码（费马小定理）

	```cpp

#include<iostream>
#include<cstdio>
#define ni(x) power(x,md-2)
using namespace std;

char rc;
void read(long long &x)
{
    x=0;rc=getchar();
    while(rc<'0'||rc>'9')
      rc=getchar();
    while(rc>='0'&&rc<='9')
      x=x*10+rc-'0',rc=getchar();
}

long long n,m,md,t,T,i,ans;//md就是题目的p 

long long power(long long a,long long n)
{
    long long ans=1;
    while(n)
    {
        if(n&1)
          ans=(ans*a)%md;
        a=(a*a)%md;
        n>>=1;
    }
    return ans;
}

int cnt;
long long check(long long x,long long detla)//除掉因子p 
{
    while(x%md==0)
      x/=md,cnt+=detla;//算分子的时候detle每次+1，分母每次-1 
    return x;
}

int main()
{
    cin>>t;
    for(T=1;T<=t;T++)
    {
        cin>>n>>m>>md;cnt=0;
        ans=1;
        for(i=n+1;i<=n+m;i++)
          ans=(ans*check(i,1))%md;
        for(i=2;i<=m;i++)
          ans=(ans*ni(check(i,-1)))%md;
        cout<<(cnt==0?ans:0)<<endl;
    }
    return 0;
}
	```
代码（线性筛）
	```cpp
#include<iostream>
#include<cstdio>
using namespace std;

char rc;
void read(long long &x)
{
    x=0;rc=getchar();
    while(rc<'0'||rc>'9')
      rc=getchar();
    while(rc>='0'&&rc<='9')
      x=x*10+rc-'0',rc=getchar();
}

long long n,m,md,t,T,i,ans,ni[200005];//md就是题目中的p 

int cnt;
long long check(long long x,long long detla)//除掉因子p 
{
    while(x%md==0)
      x/=md,cnt+=detla;//算分子的时候detle每次+1,分母每次-1 
    return x;
}

int main()
{
    cin>>t;
    for(T=1;T<=t;T++)
    {
        cin>>n>>m>>md;cnt=0;
        ni[1]=1;//这三行是线性筛逆元 
        for(i=2;i<md;i++)
          ni[i]=((-(md/i)*ni[md%i])%md+md)%md;//注意要 求正数 
        ans=1;
        for(i=n+1;i<=n+m;i++)
          ans=(ans*check(i,1))%md;
        for(i=2;i<=m;i++)
          ans=(ans*ni[check(i,-1)%md])%md;//线性筛逆元只能筛到p-1，大于p的m逆元等于m%p的逆元 
        cout<<(cnt==0?ans:0)<<endl;
    }
    return 0;
}
	```