#include<bits/stdc++.h>
using namespace std;
long long a,m,d,t,tt,lena;
string b;
int phi(long long m){//计算欧拉函数 
	long long ans=m;
	for(long long i=2;i<=sqrt(m);i++){
		if(m%i==0){
			ans=ans/i*(i-1);
			while(m%i==0) m/=i;
		}
	}
	if(m>1)	ans=ans/m*(m-1);
	return ans;
}
int power(long long a,long long b,long long p){//快速幂 
	long long base=a,ans=1;
	while(b){
		if(b&1)	ans=ans*base%p;
		base=base*base%p;
		b>>=1;
	}
	return ans;
}
bool test(int a,string b){//判断b是否大于φ(m) 
	long long bb,ba=1;
	while(a){
		lena++;
		a/=10;
	}
	if(b.length()>lena)	return 1;
	else if(b.length()<lena)	return 0;
	else{
		for(long long i=b.length();i;i--){
			bb+=(b[i-1]-'0')*ba;
			ba*=10;
		}
		if(bb>a)	return 1;
		else return 0;
	}
}
int main(){
	cin>>a>>m>>b;
	t=phi(m);
	if(test(t,b)){
		for(long long i=0;i<b.length();i++){
			d=(d*10+(b[i]-'0'))%t;
		}
		t+=d;
		cout<<power(a,t,m);
	}
	else{
		long long bb,ba=1;
		for(long long i=b.length();i;i--){
			bb+=(b[i-1]-'0')*ba;
			ba*=10;
		}
		cout<<power(a,bb,m);
	}
	return 0;
}