#include <fstream>

using namespace std;
ofstream fout("lgput.out");
ifstream fin("lgput.in");

long long n,p,i,r,f;

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

    f=n;
    r=1;

    for(i=0;(1LL<<i)<=p;i++)
    {
        if(((1LL<<i)&p)>0)
        {
            r=(r*f)%1999999973;
        }

        f=(f*f)%1999999973;
    }

    fout<<r;

    return 0;
}