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