#include <fstream>

using namespace std;

int phi(int n) {
 int rez = n;

 for (int i = 2;i * i <= n;i ++) {
  if (n % i == 0) {

   while (n % i == 0) {
    n /= i;
   }

   rez = rez / i * (i - 1);
  }
 }

 if (n != 1)
  rez = rez / n * (n - 1);
 return rez;
}

long long ridicare_la_putere(int x, int n, int exp) {
 if (exp == 0)
  return 1;
 if (exp % 2 == 0)
  return ridicare_la_putere(1LL * x * x % n, n, exp / 2) % n;
 return 1LL * x * ridicare_la_putere(1LL * x * x % n, n, (exp - 1) / 2) % n;
}

int main() {
 ifstream fin("inversmodular.in");
 ofstream fout("inversmodular.out");

 int A, n;
 fin >> A >> n;

 int exponent = phi(n);


 fout << ridicare_la_putere(A, n, exponent - 1);

 return 0;
}