#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int hatLog(int n,int hat)
{

    printf("%d %d\n",n,hat);

    if(hat!=1)
    {
        if(hat%2==0)
            return hatLog(n*n,hat/2);
        else
            return hatLog(n*n,hat/2)*n;
    }
    else
        return n;

}
int main()
{
    FILE *readfile,*writefile;
    readfile=fopen("lgput.in","r");
    writefile=fopen("lgput.out","w");

    int alap;
    int hat;

    fscanf(readfile,"%d %d",&alap,&hat);


    fprintf(writefile,"%d",hatLog(alap,hat)% 1999999973);
    return 0;
}