证明看不太懂……还是没搞明白为什么(bleq p)的时候不能加上(phi(p))……
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int a,m,phi,tmp,p,res=1,b;char ch;bool flag=0;
int main(){
// freopen("testdata.in","r",stdin);
scanf("%d%d",&a,&p),tmp=phi=p;
for(R int i=2;1ll*i*i<=tmp;++i)if(tmp%i==0){
phi=phi-phi/i;while(tmp%i==0)tmp/=i;
}if(tmp>1)phi=phi-phi/tmp;
while((ch=getc())<'0'||ch>'9');
for(;ch>='0'&&ch<='9';ch=getc()){
b=b*10+ch-'0';if(b>=phi)b%=phi,flag=1;
}if(flag)b+=phi;
for(;b;b>>=1,a=1ll*a*a%p)if(b&1)res=1ll*res*a%p;
printf("%d
",res);return 0;
}