#include<stdio.h>
long n,p;

void print(int x[2000],int n)
{int i;
for(i=0;i<n;i++)
     printf("%d",x[i]);
printf("\n");}

void copy(int u[2000],int v[2000],int n)
{int i;
for(i=0;i<n;i++)
      u[i]=v[n-1-i];}

void suma(int x[2000],int n,int y[2000],int m,int z[2000],int *k)
{int i=n-1,j=m-1,t=0;
while(i>=0&&j>=0)
       {if(x[i]+y[j]+t>9)
              {z[(*k)++]=(x[i]+y[j]+t)%10;
              t=1;}
       else
              {z[(*k)++]=x[i]+y[j]+t;
              t=0;}
       i--;
       j--;}
if(i<0&&j<0&&t!=0)
       z[(*k)++]=t;
while(i>=0)
       {if(x[i]+t>9)
              {z[(*k)++]=x[i]+t-10;
              t=1;}
       else
              {z[(*k)++]=x[i]+t;
              t=0;}
       i--;}
while(j>=0)
       {if(y[j]+t>9)
              {z[(*k)++]=y[j]+t-10;
              t=1;}
       else
              {z[(*k)++]=y[j]+t;
              t=0;}
       j--;}
if(t!=0)
       z[(*k)++]=t;}
       
long rest(int v[2000],int m,long p)
{int j=0,k,x,l=0;
long p1=p;
while(p1!=0)
       {j++;
       p1/=10;}
if(m<j)
       {for(k=0;k<m;k++)
             l=l*10+v[k];
       return l;}
for(k=0;k<j;k++)
       l=l*10+v[k];
for(k=j;k<m;k++)
       {x=l%p;
       l=x*10+v[k];}
return l%p;}

void produs(long np,int u[2000],int *p)
{int l,g,r=0,x[2000],i,j,t=0,k=0,z[2000],y[2000],v[2000],lu=1,w[2000];
long n=np;
while(n!=0)
       {x[r++]=n%10;
       n/=10;}
u[0]=0;
copy(y,x,r);
for(i=r-1;i>=0;i--)
       {for(j=r-1;j>=0;j--)
       if((y[i]*y[j]+t)>9)
              {z[k++]=(y[i]*y[j]+t)%10;
              t=(y[i]*y[j]+t)/10;}
       else
              {z[k++]=y[i]*y[j]+t;
              t=0;}
       if(t!=0)
              z[k++]=t;
       t=0;
       copy(w,z,k);
       for(l=i+1;l<r;l++)
              w[k++]=0;
       g=0;
       suma(w,k,u,lu,v,&g);
       k=0;
       lu=g;
       copy(u,v,g);
       (*p)=g;}}

void prod(int x[2000],int m,long n,int y[2000],int *p)
{int v[2000],r=0,k,j,u[2000],lu=1,t=0,w[2000],i,z[2000],l,a[2000],g,b[2000];
long n1=n;
while(n1!=0)
       {v[r++]=n1%10;
       n1/=10;}
u[0]=0;
copy(w,v,r);
for(i=r-1;i>=0;i--)
       {for(j=m-1;j>=0;j--)
       if(w[i]*x[j]+t>9)
              {z[k++]=(w[i]*x[j]+t)%10;
              t=(w[i]*x[j]+t)/10;}
       else
              {z[k++]=w[i]*x[j]+t;
              t=0;}
       if(t!=0)
              z[k++]=t;
       t=0;
       copy(a,z,k);
       for(l=i+1;l<r;l++)
              a[k++]=0;
       g=0;
       suma(a,k,y,lu,b,&g);
       k=0;
       lu=g;
       copy(y,b,g);
       (*p)=g;}}

long putere(long n,long p)
{int m,v[2000],k,w[2000];
if(p==0)
       return 1;
if(p%2==0)
       {m=0;
       produs(putere(n,p/2),v,&m);
       print(v,m);
       return rest(v,m,1999999973);}
else
       {m=0;
       k=0;
       produs(putere(n,(p-1)/2),v,&m);
       print(v,m);
       prod(v,m,n,w,&k);
       print(w,k);
       return rest(w,k,1999999973);}}

int main()
{freopen("lgput.in","r",stdin);
freopen("lgput.out","w",stdout);
scanf("%ld%ld",&n,&p);      
printf("%ld\n",putere(n,p));
fclose(stdin);
fclose(stdout);
return 0;}