#include <fstream>

using namespace std;
ifstream in("lgput.in");
ofstream out("lgput.out");
const long long MOD=1999999973;
long long n,p;//se ridica n la p

int main()
{
    in>>n>>p;
    long long prod=1;
    for(int bit=0;(1<<bit)<=p;++bit)
    {
        if((1<<bit)&p)
            prod=(prod*n)%MOD;
        n=(n*n)%MOD;
    }
    out<<prod;
    return 0;
}