#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;
    }
    nr=-1;
    while (p>0) {
        nr++;
        b2[nr]=p%2;
        p=(int) p/2;
    }
    rez=1;
    for(i=nr;i>=0;i--) {
        if (b2[i]==1) rez=(rez*valput[i])%MODD;
    }


    fprintf(fout,"%d\n",rez);
    fclose(fout);
    return 0;
}