#include<fstream>
using namespace std;

#define MAX 1999999973

int main()
{
    unsigned int i;
    unsigned long long p, n, r = 1;
    fstream in("lgput.in", fstream::in);
    fstream out("lgput.out", fstream::out);

    in>>n>>p;
    in.close();

    for(i=0; (1<<i) <= p; ++i)
    {
        if((1<<i) & p)
            r = (r*n) % MAX;
        n = (n*n) % MAX;
    }

    out<<r;
    out.close();

    return 0;
}