#include <stdio.h>
#include <math.h>

#define mod 1999999973


int main()
{
  FILE *f;
  FILE *g;

  f=fopen("lgput.in","r");
  g=fopen("lgput.out","w");



 unsigned int n,p;
 fscanf(f,"%d %d",&n,&p);
 int i=1;
 long long a=n,sol=1;
 for (i=0;(1<<i)<=p;++i)
 {
   if (((1<<i)&p)>0) {sol=(sol*a)%mod;}
   a=(a*a)%mod;

 }

 fprintf(g,"%lld\n",sol);


fclose(g);
fclose(f);
 return 0;
}