#include <iostream>
#include <fstream>
#define MOD 1999999973
using namespace std;
ifstream in("lgput.in");
ofstream out("lgput.out");

long long lgput(long long n, long long p)
{
    long long sol=1, a=n, i, m=MOD;
    for(i = 0; (1<<i) <= p; ++i){
        if(((1<<i) & p) > 0)
            sol = (sol * a) % m;
        a = (a * a) % m;
    }
    return sol;
}
int main()
{
    long long n,p;
    in>>n>>p;
    out<<lgput(n,p);
    return 0;
}