提交记录
观察到wa的点有些输出了0，但没有输出负数的情况。
并且，把int define成longlong后居然T且WA掉了。

#include<iostream>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
const int maxn=1e6+10;
LL N,M,fac[maxn][2],ftop=0,c[maxn][2];
LL exgcd(LL a,LL b,LL &x,LL &y){
	if(!b){x=1,y=0;return a;}
	LL rt=exgcd(b,a%b,x,y),x0=x;
	x=y,y=x0-a/b*y;
	return rt;
}
LL exgcd(LL a,LL b,LL &x,LL &y,LL k){
//	printf("exgcd %lld %lld %lld=>",a,b,k);
	LL fac=exgcd(a,b,x,y);
	x*=k/fac,y*=k/fac;
//	printf("%lld %lld\n",x,y);
	return fac;
}
void facen(int t){
	for(int i=2;i*i<=t;i++){
		if(t%i==0)  fac[++ftop][0]=i,fac[ftop][1]=1;
		while(t%i==0)  fac[ftop][1]*=i,t/=i;
	}
	if(t!=1)  fac[++ftop][0]=t,fac[ftop][1]=t;
}
LL qsm(LL x,LL y,int mod){
//	printf("%lld ^ %lld %% %d:",x,y,mod);
	x%=mod;LL rt=1;
	for(;y;y>>=1,x=x*x%mod)  if(y&1)  rt=rt*x%mod;
//	printf("%lld\n",rt);
	return rt;
}
LL ni(LL t,int mod){
	LL x,y,k=exgcd(t,mod,x,y),_b=mod/k;
//	printf("find <%d>*%d + <%d>*%d = %d\n",t,x,mod,y,k);
	return (x%_b+_b)%_b;
}
LL prod(LL l,LL r,int k,int mod){
	LL rt=1;//useful change
//	printf("	prod %lld to %lld jump%d %% %d ",l,r,k,mod);
	for(;l<=r;l++)  if(l%k)  rt=rt*l%mod;
//	printf("= %d\n",rt);
	return rt;
}
LL e_f(LL x,int p,int pk){
	if(!x)  return 1;
//	printf("e_f %lld %d %d\n",x,p,pk);
	LL rt=qsm(prod(1,pk,p,pk),x/pk,pk)*prod(x/pk*pk,x,p,pk)%pk*e_f(x/p,p,pk)%pk;
//	printf("%lld! without %d %% %d = %lld\n",x,p,pk,rt);
	return rt;
}
LL e_g(LL x,int p){
	if(!x)  return 0;
//	printf("e_g %lld %d = %lld\n",x,p,x/p+e_g(x/p,p));
	return x/p+e_g(x/p,p);
}
LL exlucas(LL x,LL y,int p,int pk){//C_x^y
	LL rt=e_f(x,p,pk)*ni(e_f(y,p,pk)*e_f(x-y,p,pk),pk)%pk*qsm(p,e_g(x,p)-e_g(y,p)-e_g(x-y,p),pk)%pk;
//	printf("exlucas %lld %lld %d %d=%lld\n",x,y,p,pk,rt);
//	printf("*%lld\n**%lld\n***%lld\n",e_f(x,p,pk),ni(e_f(y,p,pk)*e_f(x-y,p,pk),pk),qsm(p,e_g(x,p)-e_g(y,p)-e_g(x-y,p),pk));
//	printf("e_g\n*%lld\n**%lld\n***%lld\n",e_g(x,p),e_g(y,p),e_g(x-y,p));
	return rt;
}
LL excrt(){//debugged
	LL a=c[1][0],b=c[1][1];//a:mod
	for(int i=2;i<=ftop;i++){
//		if(c[i][1]<b)  swap(a,c[i][0]),swap(b,c[i][1]);//useless change
		LL x,y,k=exgcd(a,c[i][0],x,y,c[i][1]-b);y=-y;
		b=a*x+b,a=a/k*c[i][0],b=(b%a+a)%a;
	}
	return b;
}
int main(){
//	freopen("debug.txt","w",stdout);
	int mod;
	scanf("%lld%lld%d",&N,&M,&mod);
	facen(mod);
//	printf("%lld prime fac\n",ftop);
//	for(int i=1;i<=ftop;i++)  printf("fac %lld %lld\n",fac[i][0],fac[i][1]);
	for(int i=1;i<=ftop;i++){
		c[i][0]=fac[i][1];//m,r;base,mi
		c[i][1]=exlucas(N,M,fac[i][0],fac[i][1]);//debug
//		if(!c[i][1])  c[i][1]=c[i][0];//useless change
	}
	printf("%lld\n",excrt());
	return 0;
}