#include <fstream>
#include <cmath>
#define x 1999999973

using namespace std;

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

long long n, p, last;
long long V[35], i, sol;

int main()
{
    fin>>n>>p;
    last=log(p)/log(2);
    V[0]=n;
    for (i=1; i<=last; i++)
    {
        V[i]=V[i-1]*V[i-1];
        V[i]=V[i]%x;
    }
    sol=1;
    for (i=0; i<=last; i++)
    {
        if ((1<<i)&p)
        {
            sol*=V[i]%x;
            sol=sol%x;
        }
    }
    fout<<sol%x;
    return 0;
}
//1010101011110111100010110