#include <iostream>
#include <fstream>

using namespace std;


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

    uint32_t n,p;
    in >> n >> p;

    long long r = 1;

    for (int i = 31;i >= 0;i--)
    {
        if (p & 1 << i)
            r = (((r * r) % 1999999973) * n) % 1999999973;
        else
            r = (r * r) % 1999999973;
    }

    cout << r;
}