#include <bits/stdc++.h>
#include <cstdint>

constexpr const int32_t m = 1'999'999'973;
 
int main() {
  int64_t n, p, sol = 1ll;
  std::ifstream("lgput.in") >> n >> p;

  for (auto i = 0; (1 << i) <= p; ++i) {
    if (((1 << i) & p) > 0) {
      sol *= n;
      sol %= m;
     
      n *= n;
      n %= m;
    }
  }
  
  std::ofstream("lgput.out") << sol << '\n';
}