#include <fstream>
#include <math.h>
#define M 1999999973

using namespace std;

int lgpow_mod_m(long long n,  long long pw,  int m)
{
    long long res = 1, p = 1;
    while (p <= pw) {
        if (p & pw)
            res = res * n % m;
        n = n * n % m;
        p <<= 1;
    }
    return res;
}

int main()
{
    ifstream in("lgput.in");
    ofstream out("lgput.out");
    long long n, p;
    in>>n>>p;
    out<<lgpow_mod_m(n, p, M)<<endl;
    return 0;
}