#include <fstream>
#define numar 1999999973
using namespace std;
ifstream f("lgput.in");
ofstream g("lgput.out");
int lgput(int n,int p)
{
    int b=n,produs=1;
    for(int i=0;p>>i;++i)
    {
        if((p>>i)&1)
            {
                produs*=b;
                produs%=numar;
            }
        b*=b;
        b%=numar;
    }
    return produs;
}
int main()
{
    int N,P;
    f>>N>>P;
    N%=numar;
    P%=numar-1;
    g<<lgput(N,P);
    return 0;
}