#include <fstream>
#include <string>
#include <iostream>

const std::string kInputFileName = "lgput.in";
const std::string kOutputFileName = "lgput.out";

const long long kMod = 1999999973;

int main() {
  std::ifstream fin(kInputFileName);
  std::ofstream fout(kOutputFileName);

  int n;
  fin >> n;

  int p;
  fin >> p;

  long long result = 1;
  for (long long i = 0, n_to_i = n; (1LL << i) <= p; i++) {
    if ((1LL << i) & p) {
      result = (result * n_to_i) % kMod;
    }
    n_to_i = (n_to_i * n_to_i) % kMod;
  }

  fout << result;

  return 0;
}