#include <stdio.h>
#define mod 1999999973

int main(){
  unsigned int n,p,i;
  FILE *fin=fopen("lgput.in","r");
  FILE *fout=fopen("lgput.out","w");
  fscanf(fin,"%u%u",&n,&p);
  long long a=n,rez=1;
  for(i=0;(1<<i)<=p;i++){
     //pt fiecare bit din p (de la dreapta la stanga)
     if((1<<i & p) >0){
         //daca pe poz i in p se afla 1
         rez=(rez*a)%mod;
     }
     a=(a*a)%mod;//ridic totul la patrat
  }
  fprintf(fout,"%lld\n",rez);
return 0;
}