#include <fstream>
using namespace std;
ifstream fin("lgput.in");
ofstream fout("lgput.out");
int n,x,p;
int loga(int a, int b)
{
    if(b<0)
        return loga(1/a,-n);
    else
        if(b==0)
            return 1;
        else
            if(b==1)
                return a;
            else
                if(b%2==0)
                    return loga(a*a,b/2)%1999999973;
                else
                    if(b%2==1)
                        return a*loga(a*a,(b-1)/2)%1999999973;
}
int main()
{
fin>>n>>p;
fout<<loga(n,p);
    return 0;
}