#include<bits/stdc++.h>
#define int __int128
using namespace std;
int quickpow(int a,int n,int mod)
{
	a%=mod;
	int res=1;
	while(n>0)
	{
		if(n&1) res=(res*a)%mod;
		a=(a*a)%mod;
		n>>=1;
	}
	return res;
}
int oulaphi(int n)
{
	int ret=n;
	for(int i=2;i*i<=n;i++)
	{
		ret=n%i?ret:ret/i*(i-1);
		while(!(n%i))n/=i;
	}
	ret=n?ret/n*(n-1):ret;
	return ret;
}
int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}
int a,b,m,ans;
bool flag; 
int read(int mod)
{
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')
	{
		x*=10,x+=(c^'0');
		if(x>=mod)flag=true;
		x%=mod,c=getchar();
	}
	return x;
}
int readI()
{
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x*=10,x+=(c^'0'),c=getchar();
	return x;
}
void write(int x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
signed main()
{
	a=readI(),m=readI();
	int phi=oulaphi(m);
	b=read(phi);
	if(flag)b+=phi;
	write(quickpow(a,b,m));
	return 0;
}