拓展Lucas
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#define MAXN 100000+10
#define ll long long
#define pb push_back
#define ft first
#define sc second
#define mp make_pair
using namespace std;
void extgcd(ll a,ll b,ll &x,ll &y){
if(!b){x=,y=;}
else{
ll xx,yy;
extgcd(b,a%b,xx,yy);
x=yy;
y=xx-a/b*yy;
}
}
ll Inv(ll a,ll b){
ll x,y;
extgcd(a,b,x,y);
x=(x%b+b)%b;
if(!x)x+=b;
return x;
}
ll Pow(ll a,ll b,ll p){
ll ret=1LL;
while(b){
if(b&){(ret*=a)%=p;}
(a*=a)%=p;
b>>=;
}
return ret;
}
ll fac(ll n,ll pi,ll pk){
if(!n)return 1LL;
ll ret=1LL;
for(ll i=;i<pk;i++){
if(i%pi)(ret*=i)%=pk;
}
ret=Pow(ret,n/pk,pk);
for(ll i=;i<=(n%pk);i++){
if(i%pi)(ret*=i)%=pk;
}
return ret*fac(n/pi,pi,pk)%pk;
//每隔pi拿走一个,所以是n/pi,不是n/pk
}
ll C(ll n,ll m,ll pi,ll pk){
ll a=fac(n,pi,pk),b=fac(m,pi,pk),c=fac(n-m,pi,pk);
ll t=0LL;
for(ll i=n/pi;i;i/=pi)t+=i;
for(ll i=m/pi;i;i/=pi)t-=i;
for(ll i=(n-m)/pi;i;i/=pi)t-=i;
ll ret=a*Inv(b,pk)*Inv(c,pk)%pk;
(ret*=Pow(pi,t,pk))%=pk;
return ret;
}
ll n,m,p;
int main()
{
ll ans=0LL;
scanf("%lld%lld%lld",&n,&m,&p);
for(ll x=p,i=;i<=p;i++){
if(x%i==){
ll pk=;
while(x%i==){
pk*=i;
x/=i;
}
ll t=C(n,m,i,pk);
(t*=(p/pk))%=p;
(t*=Inv(p/pk,pk))%=p;
(ans+=t)%=p;
}
}
printf("%lld\n",ans);
return ;
}