#include <fstream>

using namespace std;
ifstream fin("lgput.in");
ofstream fout("lgput.out");

long long result;
int N,P;


int main()
{
    fin>>N>>P;
    if(N==0)fout<<0;
    else if(N==1 || P==0)fout<<1;
    else if(P==1)fout<<N;
    else {

        result=1;

            for(int i=0; (i<<1)<=P ; ++ i){
                if( ((1<<i) & P) > 0)
                    result = (result * N) % 1999999973;
                N=(N*N)%1999999973;
            }

    fout<<result;
    }

}