#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read(ll m){
	ll x=0;
	ll tt=0;
	char ch=getchar();
	while(!isdigit(ch)){
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+ch-'0';
		if(x>=m){
			tt=1;
		}
		x%=m;
		ch=getchar();
	}
	if(tt==1){
		return x+m;
	}
	return x;
}
ll b[2000010];
ll judge[10001000];
ll prime[10001000];
ll phi(ll x){
	ll ans=x;
	for(ll 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;
}
ll fastPow(ll n,ll x,ll MOD){
	ll ans=1;
	ll tmp=n;
	while(x>0){
		if(x&1){
			ans*=tmp;
			ans%=MOD;
		}
		tmp*=tmp;
		tmp%=MOD;
		x>>=1;
	}
	return ans;
}
int main(){
	ll a,m,b;
	scanf("%lld%lld",&a,&m);
	ll c=read(m);
	ll ans=0;
	ll cc=phi(m);
	if(c<phi(m)){
		ans=fastPow(a,c,m);
	}
	else{
		ans=fastPow(a,c%phi(m)+phi(m),m);
	}
	printf("%lld",ans);
	return 0;
}