#include<bits/stdc++.h>
#define ll long long
#define gc getchar()
using namespace std;
char c;
int a,m;
int m2;
int use;
int bm;
bool flag;
void peppa(){
bm=bm*10ll+(c^'0');
}
ll qPow(int num,int cnt){
int ans=1;
for(;cnt;cnt/=2,num=(ll)(num*num)%m){
if((cnt%2)){
ans=(ll)(ans*num)%m;
}
}
return ans;
}
int main(){
scanf("%d%d",&a,&m);
a%=m;
m2=m;
use=1;
for(int i=2;i*i<=m2;++i){
if((m2%i)){
continue;
}
use*=i-1;
m2/=i;
while(!(m2%i)){
use*=i,
m2/=i;
}
}
if(m2>1){
use*=m2-1;
}
while((c=gc)<'0'||c>'9');//跳过
while(peppa(),(c=gc)>='0'&&c<='9'){
if(bm>=use){
flag=1;
bm%=use;
}
}
if(bm>=use){
flag=1;
bm%=use;
}
if(flag){
bm+=use;
}
cout<<qPow(a,bm);
return 0;
}
/*
*/
用了快速幂，用了快读，28分WA，求助