#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
#define lll long long
lll a,b,m;
lll ans=0;
lll oula(lll x)
{
	lll rea=x;
	for(lll i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			rea-=rea/i;
			while(x%i==0)
			{
				x/=i;
			}
		}
	}
	if(x>1)
	{
		rea=rea-rea/x;
	}
	return rea;
}
int main()
{
	lll bb=0;
	cin>>a>>m;
	lll phi=oula(m);
	lll g=__gcd(a,m);
	string b;
	cin>>b;
	bb=0;
	bool f=0;
	for(lll i=0;i<b.size();i++)
	{
		ans*=10;
		ans+=int(b[i]-'0');
		bb*=10;
		bb+=int(b[i]-'0');
		ans%=phi;
	}
	lll aa=0;
	if(g==1)
	{
		aa=a;
		for(lll i=1;i<ans;i++)
		{
			f=1;
			aa*=a;
			aa%=m;
		}
		if(f==0)
		{
			cout<<(long long)pow(a,bb)%m<<endl;
			return 0;
		}
		cout<<aa%m<<endl;
	}
	else
	{
		
		aa=a;
		if(ans<phi)
		{
			for(lll i=1;i<ans;i++)
			{
				f=1;
				aa*=a;
				aa%=m;
			}
			if(f==0)
			{
				cout<<(long long)pow(a,bb)%m<<endl;
				return 0;
			}
			cout<<aa%m<<endl;
		}
		else
		{
			for(lll i=1;i<ans+phi;i++)
			{
				f=1;
				aa*=a;
				aa%=m;
			}
			if(f==0)
			{
				cout<<(long long)pow(a,bb)%m<<endl;
				return 0;
			}
			cout<<aa%m<<endl;
		}
	}
	return 0;
}