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

#define rep(i, n) for(int i = 0; i < n; i++)
#define repa(i, l, r) for (int i = l; i < r; i++)
#define repd(i, r, l) for (int i = r; i > l; i--)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

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

const int mod = 1999999973;

int main(void) {
  ll N, P;
  fin >> N >> P;
  ll a = N;
  ll res = 1;
  for(int i = 0; (1<<i) <= P; i++) {
    if ((1<<i) & P)
      res = (res * a) % mod;
    a = (a * a) % mod;
  }
  fout << res << endl;

  return 0;
}