#include <cstdio>
#include <cassert>
#define Mod 1999999973
#define InFile "lgput.in"
#define OutFile "lgput.out"

using namespace std;

long long n, p, a, sol=1;

int main()
{
  int i;
  assert (freopen (InFile, "r", stdin));
  assert (freopen (OutFile, "w", stdout));
  scanf ("%lld %lld\n", &n, &p);
  a=n;
  for (i=0; (1<<i)<=p; i++)
  {
    if (p & (1<<i))
      sol=(sol*a)%Mod;
    a=(a*a)%Mod;
  }
  printf ("%lld\n", sol);
  return 0;
}