//https://infoarena.ro/problema/lgput
#include <fstream>
using namespace std;
ifstream fin("lgput.in");
ofstream fout("lgput.out");
long long result=1;
#define Nmax 1999999973
int main(void)
{
    long long n,p;
    fin>>n>>p;
    n=n%Nmax;
    while(p)
    {
        if(p%2==1)
            result=result*n%Nmax;
        result=result*result%Nmax;
        p=p/2;
    }
    fout<<result;
    return 0;
}