#include<bits/stdc++.h> 
using namespace std;
const int N=32768;
int p;
inline int read()//快读不(╯▽╰)好香~~	 
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-'){f=-1;}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+(ch-48);
		ch=getchar();
	}
	return x*f;
}
int a,m,ans=1,tmp,phi,b=0;
char ch;
bool fg;
/*int kk(int a,int b)//快速幂QAQ 
{
	int base=a%p,ans=1;
	while(b>0)
	{
		if(b&1) ans*=base;
		ans%=p;
		base*=base;
		base%=p;
		b>>=1;
	}
	return ans;
}*/
int main()
{
	scanf("%d%d",&a,&m);
	phi=tmp=m;
	for(int i=2;i*i<=m;++i)
	{
		if(tmp%i==0)
		{
			phi=phi-phi/i;
			while(tmp%i==0) tmp/=i;
		}
	}
	if(tmp>1) phi=phi-(phi/tmp);
	while(!isdigit(ch=getchar()));//是十进制.. 
	for(;isdigit(ch);ch=getchar())
	{
		b=(b<<1)+(b<<3)+(ch-48);
		if(b>=phi)
		{
			fg=true;
			b%=phi;
		}
	}
	if(fg)
	{
		b=b+phi;
	}
	for(int i=20;i>=0;--i)//快速幂 
	{
		ans=1ll*ans*ans%m;
		if(b&(1<<i)) ans=1ll*ans*a%m;//转成longlong类型 
	}
	printf("%d",ans);
	return 0;	
}