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