#include<iostream>
#include<math.h>
using namespace std;

unsigned long int n;
unsigned long int p;
unsigned long int nr = 1;
unsigned long int p2;

void inmultire(void)
{
     p2 = (int)sqrt(p);
     nr = n;
     for(unsigned long int i=1;i<=p2;i++)
        nr = (nr*nr)%4000000000;
     p2 *= p2;
     for(unsigned long int i=1;i<=p-p2;i++)
        nr = (nr*n)%4000000000;
}

void citire(void)
{
     FILE *f = fopen("lgput.in","r");
     
     fscanf(f,"%d %d",&n,&p);
     
     fclose(f);
}

int main()
{
    FILE *f = fopen("lgput.out","w");
    
    citire();
    inmultire();
    fprintf(f,"%u",nr%1999999973);
    
    fclose(f);
}