#include<fstream>

using namespace std;

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

long long n;

long long ridic(long long x, long long p)
{
 if (p == 1)
  return (x %n);
 long long aux = ridic(x, p / 2);

 if (p % 2 == 0)
  return ((aux*aux) % n);
 else
  return ((((aux * aux) % n) *x) % n);
}

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

 for (long long i = 2; i*i <= n; ++i)
 {
  if (n %i == 0)
  {
   while (n %i == 0)
    n /= i;
   rez -= (rez / i);
  }
 }

 if (n > 1)
  rez -= (rez / n);

 return rez;
}


int main()
{
 long long a;
 f >> a >> n;

 long long ph = phi(n);

 long long inv_m = ridic(a, ph - 1);

 g << inv_m << "\n";

 return 0;
}