#include <fstream>

using namespace std;

ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

int a, n;

int inversModular(int nr){
  int cpy = nr;
  int invm = nr;

  if (cpy % 2 == 0)
    invm = invm * (2 - 1) / 2;

  while (cpy % 2 == 0)
    cpy /= 2;

  for (int i = 3; i * i <= nr; i += 2){
    if (cpy % i == 0)
      invm = invm * (i - 1) / i;
    while (cpy % i == 0)
      cpy /= i;
  }

  if (cpy != 1)
    invm = invm * (cpy - 1) / cpy;

  return invm;
}

int exp(long long int a, long long int b){
  long long int ret = 1;
  while (b){
    if (b & 1)
      ret = (1LL * ret * a);
    b >>= 1;
    a = 1LL * a;
  }

  return ret;
}

int main(){
  in >> a >> n;

  int invm = inversModular(n);

  out << exp(a, invm - 1) % n;

  return 0;
}