#include <fstream>
#include <algorithm>
#include <cmath>
#define nr 1999999973

using namespace std;

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

int n,p,i,r;
long long int s,a;

int main()
{
    fin >> n >> p;
    a = n;
    r = 1;
  for (i = 0; (1<<i) <= p; ++ i)
    {
        if ( ((1<<i) & p) > 0)
            r= (r * a) % nr;

            a=(a * a) % nr;
    }
    fout << r;
}