#include <iostream>
#include <fstream>

int64_t log_pow(int64_t base, int64_t exp, int64_t& MOD) {
  int64_t temp = base;
  int64_t ans = 1;

  while (exp) {
    if (exp & 1)
      ans = (ans * temp) % MOD;

    temp = (temp * temp) % MOD;
    exp >>= 1;
  }

  return ans;
}

int64_t phi(int64_t n) {
  int div = 2, exp = 0;
  int64_t ans = 1;

  if (n % div == 0) {
    while (n % div == 0) {
      ++exp;
      n /= div;
    }

    ans *= log_pow(div, exp - 1, n) * (div - 1);
  }

  div = 1;
  exp = 0;
  while (n != 1) {
    div += 2;

    if (div * div > n)
      div = n;

    if (n % div == 0) {
      while (n % div == 0) {
        ++exp;
        n /= div;
      }

      ans *= log_pow(div, exp - 1, n) * (div - 1);
    }
  }

  return ans;
}

int main() {
  std::ifstream in("inversmodular.in");
  std::ofstream out("inversmodular.out");

  int64_t a, n;
  in >> a >> n;

  int64_t exp = phi(n) - 1;

  out << log_pow(a, exp, n);

  return 0;
}