类比：
类比一下所有可以用来求组合数的方法：
- 预处理：可以有效处理O(1e6)?数据，弊端是不能存在模数不为质数和
中
的情况，p为模数
- 帕斯卡恒等式：可以处理O(1e3)的数据，依靠dp，没有模数限制
- Lucas定理：可以求n，m较大而p较小的情况，递归在O(
)
O(?)来求，弊端是模数一定是质数
- 扩展Lucas：跟lucas无关，是中国剩余定理+预处理阶乘，注意，在题中保证p不是质数而且还很大的情况下，能保证p的质因数幂在1e5~6范围内，考虑使用扩展Lucas
补充一个：BSGS是求：最小正整数x，前提是
而扩展BSGS就不用
正题：?
?
?
代码如下：?
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdlib>
#include<iomanip>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e6+5;
inline ll read()
{
ll x=0,y=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') y=-1; c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*y;
}
inline ll quick_pow(ll a,ll b,ll p)
{
ll ans=1%p,tmp=a%p;
while(b)
{
if(b&1) ans=(ans*tmp)%p;
tmp=(tmp*tmp)%p;
b>>=1;
}
return ans%p;
}
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b) {x=1,y=0; return ;}
exgcd(b,a%b,x,y);
ll tmp=x; x=y; y=tmp-(a/b)*y;
return ;
}
ll inv(ll a,ll p)
{
ll x,y;
exgcd(a,p,x,y);
return (x%p+p)%p;
}
//k为n!中有最多多少因数x相乘
//下一行：递归去求n!除以x的因数幂(x^k)后剩下的数
ll fac(ll n,ll pi,ll pk)
{
if(!n) return 1; //0!=1
ll ret=1;
for(ll i=1;i<pk;i++)
if(i%pi) ret=(ret*i)%pk;
ret=quick_pow(ret,n/pk,pk);
for(ll i=1;i<=n%pk;i++)
if(i%pi) ret=(ret*i)%pk;
return ret*fac(n/pi,pi,pk)%pk;
}
//pk=pi^x pi是质数
ll C(ll n,ll m,ll pi,ll pk)
{
int f1=fac(n,pi,pk);
int f2=fac(m,pi,pk);
int f3=fac(n-m,pi,pk);
ll tot(0);
//以下三句均为求n!里有多少个因数x
for(ll i=n;i;i/=pi) tot+=(i/pi);
for(ll i=m;i;i/=pi) tot-=(i/pi);
for(ll i=n-m;i;i/=pi) tot-=(i/pi);
return f1*inv(f2,pk)%pk*inv(f3,pk)%pk*quick_pow(pi,tot,pk)%pk;
}
ll CRT(ll x,ll p,ll mod) //mod是所有互质模数乘积
{return x*(mod/p)%mod*inv(mod/p,p)%mod;}
ll exlucas(ll n,ll m,ll p)
{
ll now=p,k,ans(0);
for(ll i=2;i*i<=p;i++)
{
if(now%i) continue;
k=1; while(now%i==0) k*=i,now/=i;
ans=(ans+CRT(C(n,m,i,k),k,p))%p;
}
if(now>1)
ans=(ans+CRT(C(n,m,now,now),now,p))%p;
return ans;
}
ll n,m,p;
int main()
{
n=read(); m=read(); p=read();
printf("%lld\n",exlucas(n,m,p));
return 0;
}
