#include <fstream>

using namespace std;

unsigned int n,p,md=1999999973,put[35],sol;

int main()
{
    ifstream in ("lgput.in");
    ofstream out ("lgput.out");

    in>>n>>p;

    n=n%md;

    sol=1;

    while (p>0) { ++put[0]; put[put[0]]=p%2; p=p/2; }

    for (int i=put[0];i>0;--i)
    {
        sol=(1LL*sol*sol)%md;
        if (put[i]==1) sol=(1LL*sol*n)%md;
    }

    out<<sol;

    in.close();
    out.close();
    return 0;
}