#include <fstream>
using namespace std;

int main()
{
    unsigned int i;
    unsigned long long sol=1, n, p;
    ifstream f("lgput.in");
    ofstream g("lgput.out");
    f >> n >> p;
    for (i=0;(1<<i) <= p;i++)
    {
        if ((1<<i) & p)
            sol = sol*n % 1999999973;
        n*=n % 1999999973;
    }
    g << sol;
    return 0;
}