#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ifstream fin("lgput.in");
    long long rasp=1,pn;
    int n,p,i,cif;
    fin>>n>>p;
    pn=n;
    do
    {
        cif=p%2;
        p/=2;
        if(cif)
            rasp=rasp*pn%1999999973;
        pn=pn*pn%1999999973;
    }while(p);
    ofstream fout("lgput.out");
    fout<<rasp;
    return 0;
}