#include <stdio.h>
#include <stdlib.h>
long long exp_log_rec(long long x, long long n)
{
    if(n < 0) return exp_log_rec(1.0 / x, -n);
    if(n == 0)  return 1;
    if(n % 2 == 0) return exp_log_rec(x*x%1999999973, n/2);
    if(n % 2 == 1) return (x * (exp_log_rec(x*x%1999999973,n/2)))%1999999973;
}
int main(void)
{
    FILE *f=NULL;
    long long x,n;
    if((f=fopen("lgput.in","r"))==NULL)
    {
        perror(NULL);
        exit(-1);
    }
    fscanf(f,"%lld %lld",&x,&n);
    if(fclose(f)!=0)
    {
        perror(NULL);
        exit(-1);
    }
    if((f=fopen("lgput.out","w"))==NULL)
    {
        perror(NULL);
        exit(-1);
    }
    fprintf(f,"%lld",exp_log_rec(x,n)%1999999973);
    if(fclose(f)!=0)
    {
        perror(NULL);
        exit(-1);
    }
    return 0;
}