#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);
 p/=pp;
 if(p==1)
 {
  attnr(V1,rest);
  prod(V1,V2,T);
  imp(T,A,V1,V2);
  nr(temp,V2);
  return temp;
  }
 else
  {
   nr(u,V2);
   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;
 }