#include <fstream>

using namespace std;

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

int a, n;

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

  int fi = n;
  int aux = n;

  int d = 2;
  if (aux % d == 0)
    fi = fi / d * (d - 1);

  while (aux % d == 0)
    aux /= d;

  d ++;

  for (d; d * d <= n; d += 2){
    if (aux % d == 0){
      fi = fi / d * (d - 1);

      while (aux % d == 0)
        aux /= d;
    }
  }

  if (aux > 1)
    fi = fi / aux * (aux - 1);

  fi --;

  int invm = 1;

  while (fi){
    if (fi & 1)
      invm = 1LL * invm * a % n;

    a = 1LL * a * a % n;
    fi /= 2;
  }

  out << invm;

  return 0;
}