// http://www.infoarena.ro/problema/lgput
#include <fstream>
#include <iostream>

using namespace std;

const int M = 1999999973;

long long fast_pow(long long n, long long p) {
  if (p == 1)
    return n;
  if (p % 2 == 0) {
    long long pp = fast_pow(n, p / 2);
    return (pp * pp) % M;
  }
  return (n * fast_pow(n, p - 1)) %  M;
}

int main() {
  ifstream f("lgput.in");
  ofstream g("lgput.out");

  long long n, p;
  while (f >> n) {
    f >> p;
    std::cout << n << " " << p << std::endl;
    g << fast_pow(n, p) << "\n";
  }

  return 0;
}