记录编号	337208	评测结果	AAAAAAAAWT
题目名称	[HZOI 2016]定约servant	最终得分	80
用户昵称	Go灬Fire	是否通过	未通过
代码语言	C++	运行时间	5.437 s
提交时间	2016-11-04 07:45:53	内存使用	158.21 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
#define LL unsigned long long
#define Begin freopen("servant.in","r",stdin);freopen("servant.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
const int maxn=1e7+30;
LL n,m,mod,fang,phi; 
LL jc[maxn];
bool vis[maxn*10];
int Prime[maxn/10],cnt;
struct Matrix{
	LL a[3][3];
	void Init(LL x){
		for(int i=0;i<=2;i++)for(int j=0;j<=2;j++)a[i][j]=0;
		for(int i=1;i<=2;i++)a[i][i]=x;
	}
	Matrix operator * (const Matrix & b)const{
		Matrix c;
		for(int i=1;i<=2;i++){
			for(int j=1;j<=2;j++){
				c.a[i][j]=0;
				for(int k=1;k<=2;k++){
					c.a[i][j]+=a[i][k]*b.a[k][j];
					c.a[i][j]%=phi;
				}
			}
		}
		return c;
	}
};
void Init();
LL qpow(LL x){
	Matrix ans;ans.Init(0);ans.a[1][1]=1;ans.a[1][2]=1;
	Matrix a;a.Init(0);a.a[1][1]=a.a[1][2]=a.a[2][1]=1;
	while(x){
		if(x&1)ans=ans*a;
		a=a*a;x>>=1;
	}
	return ans.a[1][1]*ans.a[1][2]; 
}
LL qpow(LL x,LL h){
	LL ans=1;
	while(h){
		if(h&1)ans*=x,ans%=mod;
		x*=x;x%=mod;h>>=1;
	}
	return ans;
}
int Gcd(LL x,int LL y){
	int r=x%y; 
	while(r){
		x=y;y=r;r=x%y;
	}
	return y;
}
LL C(LL n,LL m){
	if(n<m)return 0;
	LL tot=(jc[n]%mod*qpow(jc[m]*jc[n-m]%mod,mod-2)%mod);tot%=mod;
	return tot;
}
LL Lucas(LL n,LL m){
	if(m==0)return 1;
	//printf("<<%lld %lld>>",n,m);
	return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
}
LL Phi(LL x){
	LL tem=x,ans=x;
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			ans=ans/i*(i-1);
			while(x%i==0)x/=i;
		}
	}
	if(x>1){
		ans=ans/x*(x-1);
	}
	return ans;
}
void Get_Prime(){
	for(int i=2;i<=n+1000;i++){
		if(!vis[i]){
			Prime[++cnt]=i;
			//printf("%d %d ",i,cnt);
			if(i>n)break;
		}
		for(int j=1;j<=cnt;j++){
			if(i*Prime[j]>n+1000)break;
			vis[i*Prime[j]]=1;
			if(i%Prime[j]==0)break;
		}
	}
	//printf("%d\n",Prime[cnt]);
}
LL Count(LL date,LL x){
	LL num=0;
	while(date){
		num+=date/x;
		date/=x;
	}
	return num;
}
LL Get(LL x,LL y){
	LL ans=1;
	for(int i=1;Prime[i]<=n;i++){
		int num=Count(x,Prime[i])-Count(y,Prime[i])-Count(x-y,Prime[i]);
		ans=ans*qpow(Prime[i],num);ans%=mod; 
	}
	return ans;
}
void Deal_He(){
	Get_Prime();
	LL ans=0;
	ans+=Get(n,m-1);ans+=Get(n,0);
	/*for(LL i=1;i<=m+1;i++){
		if(Gcd(m,i)==1){
			ans+=Get(n,i-1);ans%=mod;
		}
	}*/
	ans=qpow(ans,fang);ans%=mod;
	printf("%llu\n",ans);
}
int main(){
    Begin;
    scanf("%llu%llu%llu",&n,&m,&mod);
    phi=Phi(mod);
	fang=qpow(n-1);fang=fang%(phi);fang+=phi;
	bool flag=0;
	if(phi==mod-1)Init();
	else Deal_He();
    getchar();getchar();
    //for(;;);
    End;
    return 0;
}
void Init(){
	jc[0]=1;//调死我了 
	for(int i=1;i<=min(n,mod)+3;i++)jc[i]=jc[i-1]*i,jc[i]%=mod;
	LL ans=0;
	for(LL i=1;i<=m+1;i++){
		if(Gcd(m,i)==1){
			ans+=Lucas(n,i-1);ans%=mod;
		}
	}
	ans=qpow(ans,fang);ans%=mod;
	printf("%llu\n",ans);
}