#include <iostream>
#include <stdio.h>

using namespace std;

#define MOD 1999999973

FILE *fin=fopen("lgput.in","r"),*fout=fopen("lgput.out","w");
int n,p,i,j,nr,rez,valput[34];
char b2[34];

int main()
{
    fscanf(fin,"%d %d",&n,&p);
    valput[0]=n;
    for(i=1;i<=32;i++) {
        valput[i]=valput[i-1]*valput[i-1]%MOD;
    }
    j=p;
    while (j>0) {
        b2[nr]=j%2;
        j=(int) j/2;
        nr++;
    }
    nr--;
    rez=1;
  //  for(i=nr;i>=0;i--) {cout<<" "<<(int)b2[i];} cout<<"\n";
 //   for(i=nr;i>=0;i--) {cout<<" "<<valput[i];} cout<<"\n";
    for(i=nr;i>=0;i--) {
        if (b2[i]==1) rez=(rez*valput[i])%MOD;
    }
    fprintf(fout,"%d\n",rez);
    fclose(fout);
    return 0;
}