#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 = x, d;

  if (x % 2 == 0) {
    while (x % 2 == 0) x = x >> 1;
    ret = (ret >> 1);
  }

  for (d = 3; d * d <= x; d += 2) {
    if (x % d == 0) {
      while (x % d == 0) x /= d;
      ret = (ret / d) * (d - 1);
    }
  }

  if (x != 1) ret = (ret / x) * (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;
}