#include <fstream>

using ull = unsigned long long;

ull fi(ull);
ull putere_mod(ull, ull, ull);

int main() {
  ull a, n;

  std::ifstream fin("inversmodular.in");

  fin >> a >> n;

  fin.close();

  std::ofstream fout("inversmodular.out");

  fout << putere_mod(a, fi(n) - 1, n) << '\n';

  fout.close();

  return 0;
}

ull fi(ull x) {
  ull ret = 1, d = 3;
  bool ok = false;

  while (x % 2 == 0) {
    ret = ret << 1;
    x = x >> 1;
    ok = true;
  }

  if (ok) ret = (ret >> 1);

  ok = false;
  while (d * d <= x) {
    if (x % d == 0) {
      ret *= d;
      x /= d;
      ok = true;
    }
    else {
      if (ok) ret = (ret / d) * (d - 1);
      ok = false;
      d += 2;
    }
  }

  if (ok) ret = (ret / d) * (d - 1);

  if (x) ret *= (x - 1);

  return ret;
}

ull putere_mod(ull b, ull p, ull m) {
  if (p == 0) return 1;
  if (p % 2 == 0) return putere_mod(b * b, p / 2, m) % m;
  return (b * putere_mod(b * b, p / 2, m)) % m;
}