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

unsigned long hatLog(unsigned long n,unsigned long hat)
{

    printf("%lu %lu\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");

    unsigned long alap;
    unsigned long hat;

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


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