#include<fstream.h>
#include<math.h>
typedef long Huge[150];
long a=1999999973;
long A[30];
void attnr(Huge h, long x)
{
h[0]=0;
while(x)
{
h[++h[0]]=x%10;
x/=10;
}
}
void attv(Huge h, Huge g)
{
for(int i=0;i<=g[0];i++)h[i]=g[i];
}
int comp(Huge h, Huge g)
{
while(h[0]&&!h[h[0]])h[0]--;
while(g[0]&&!g[g[0]])g[0]--;
if(h[0]<g[0]) return -1;
else if(h[0]>g[0]) return 1;
int t=h[0];
while(h[t]==g[t]&&t>=1)t--;
if(!t) return 0;
if(h[t]>g[t])return 1;
else return -1;
}
void ad(Huge h, Huge g)
{
int i,trans=0;
if(g[0]>h[0])
{
for(i=h[0]+1;i<=g[0];i++)h[i]=0;
h[0]=g[0];
}
else
for(i=g[0]+1;i<=h[0];i++)g[i]=0;
for(i=1;i<=h[0];i++)
{
h[i]+=g[i]+trans;
trans=h[i]/10;
h[i]%=10;
}
if(trans)
{
h[0]++;
h[h[0]]=trans;
}
}
void dif(Huge h, Huge g)
{
int i;
for(i=g[0]+1;i<=h[0];i++) g[i]=0;
int trans=0,d;
for(i=1;i<=h[0];i++)
{
d=h[i]-g[i]-trans;
if(d>=0)
{
trans=0;
h[i]=d;
}
else
{
trans=1;
h[i]=10+d;
}
}
while(h[0]&&!h[h[0]])h[0]--;
}
void inm10(Huge h, int e)
{
int i;
for(i=h[0];i>=1;i--)h[i+e]=h[i];
for(i=1;i<=e;i++)h[i]=0;
h[0]+=e;
}
void imp10(Huge h, int e)
{
int i;
for(i=e+1;i<=h[0];i++)h[i-e]=h[i];
h[0]-=e;
}
void prod(Huge h, Huge g, Huge p)
{
int i,j,trans=0;
p[0]=h[0]+g[0]-1;
for(i=1;i<=h[0]+g[0];i++)p[i]=0;
for(i=1;i<=h[0];i++)
for(j=1;j<=g[0];j++)
p[i+j-1]+=h[i]*g[j];
for(i=1;i<=p[0];i++)
{
p[i]+=trans;
trans=p[i]/10;
p[i]%=10;
}
if(trans)
{
p[0]++;
p[p[0]]=trans;
}
while(p[0]&&!p[p[0]])p[0]--;
}
void imp(Huge h, Huge g, Huge p, Huge r)
{
int i;
r[0]=0;
p[0]=h[0];
for(i=h[0];i>=1;i--)
{
inm10(r,1);
r[1]=h[i];
p[i]=0;
while(comp(g,r)!=1)
{
p[i]++;
dif(r,g);
}
}
while(p[0]>1&&!p[p[0]])p[0]--;
}
void nr(long &n, Huge N)
{
int i;
n=0;
for(i=N[0];i;i--)
n=n*10+N[i];
}
long fct(long n, long p)
{
long temp,pp=1,r[30],N[30],V1[30],V2[30],RE[30],REZ[30],s[30],rest,u,T[30];
if(n==1)return 1;
attnr(N,n);
attv(s,N);
while(comp(s,A)!=1)
{
prod(s,N,r);
attv(s,r);
pp++;
if(p==pp)
{
imp(s,A,V1,V2);
nr(u,V2);
return u;
}
}
rest=pow(n,(p%pp));
imp(s,A,V1,V2);
nr(u,V2);
p/=pp;
if(p==1)
{
attnr(V1,rest);
prod(V1,V2,T);
imp(T,A,V1,V2);
nr(temp,V2);
return temp;
}
else
{
temp=fct(u,p);
attnr(T,temp);
attnr(RE,rest);
prod(T,RE,REZ);
imp(REZ,A,V1,V2);
nr(temp,V2);
return temp;
}
}
int main()
{
long n,p;
ifstream f("lgput.in");
ofstream g("lgput.out");
f>>n>>p;
attnr(A,a);
g<<fct(n,p);
return 0;
}