#include <fstream>
using namespace std;

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

long long b, p, sol;

int main()
{
    long long i;

    fin>>b>>p;

    sol=1;
    for (i=0; (1<<i)<=p; i++)
    {
        if ( ((1<<i)&p) > 0)
            sol=(sol*b)%1999999973;
        b=(b*b)%1999999973;
    }

    fout<<sol;

    fin.close();
    fout.close();
    return 0;
}