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

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

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

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

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