#include <fstream>
#define m 1999999973

using namespace std;

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

typedef unsigned long long ull;

ull N, P, sol = 1;

int main()
{
    in >> N >> P;
    for(ull k = 0; (1 << k) <= P; ++k)
    {
        if((1 << k) & P)
            sol = (sol * N) % m;
        N = (N * N) % m;
    }
    out << sol;
    return 0;
}