#include <iostream>
#include <fstream>

#define infile "lgput.in"
#define outfile "lgput.out"
#define mod 1999999973

using namespace std;

ifstream in(infile);
ofstream out(outfile);

long long x, p;

int main()
{

    in >> x >> p;

    int r=1;

    for(int t=p; t; t/=2){
        if(t%2){
            r = (r*x) % mod;
        }
        x = (x*x) % mod;
    }

    out << r << '\n';

    return 0;
}