#include <fstream>
#include <string.h>

using namespace std;

ifstream in ("lgput.in");
ofstream out ("lgput.out");

long long  n,p,x,y,pow=1;

int main()
{
    in >> n >> p;

    x=n;

    while(pow<p)
    {
        y=x;
        x=x*x;
        pow=pow*2;
        x=x%1999999973;
    }

    if(pow==p)
    {
        out << x;
        return 0;
    }
    x=x/y;
    pow=pow/2;
    while(pow<=p)
    {
        x=x*n;
        x=x%1999999973;
        pow++;
    }

    out << x;
    return 0;
}