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

using namespace std;

#define MODD 1999999973

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

int main()
{
    fscanf(fin,"%d %d",&n,&p);
    valput[0]=n;
    for(i=1;i<=34;i++) {
        valput[i]=(valput[i-1]*valput[i-1])%MODD;
    }
    while (p>0) {
        b2[nr]=p%2;
        p=(int) p/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])%MODD;
    }
    fprintf(fout,"%d\n",rez);
    fclose(fout);
    return 0;
}