RT

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define of(i,m,n)	for(register ll i=m;i>=n;i--)
#define fo(i,m,n)	for(register ll i=m;i<=n;i++)
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
inline ull mul(ull a,ull b){
	ull ans;
	__asm__ ("mulq %2;divq %3" : "=d" (ans) : "a" (a), "m" (b), "m" (mod));
	return ans;
}
ll ksm(ll a,ll b,ll mms){
	ll ans=1;
	while(b){
		if(b&1)ans*=a;
		a*=a;
		a%=mms;ans%=mms;
		b>>=1;
	}
	return ans;
}
#define co(p) if(n%p==0){\
		len++;\
		while(n%p==0)n/=p,s[len][0]=p,s[len][1]++;\
	}
ll s[430][2];
ll len=0;
ll phwwi(ll n){
	co(2)
	ll ans=n;
	for(ll i=3;i*i<=n;i+=2)co(i)
	if(n!=1)s[++len][0]=n,s[len][1]=1;
	fo(i,1,len){
		ans*=s[i][0]-1;
	}
	fo(i,1,len){
		ans/=s[i][0];
	}
	return ans;
}
int main(){
	int n=read(),m=read();
	int phi=phwwi(m),ans=0;
	//cout<<phi<<endl;
	char c=getchar();
	while(isdigit(c))ans*=10,ans+=c-'0',ans%=phi,c=getchar();
	ans+=phi;
	cout<<ksm(n,ans,m);
	return 0;
}