#include <fstream>

using namespace std;

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

long long a, n;

inline long long lgput(long long x, long long y)
{
 long long sol = 1;
 while (y)
 {
  if (y & 1)
   sol = (sol * x) % n;
  x = ((x % n) * (x % n)) % n;
  y >>= 1;
 }
 return sol;
}

inline long long phi(int n)
{
 long long rez = n;
 if (n % 2 == 0)
 {
  rez >>= 1;
  while (n % 2 == 0)
   n >>= 1;
 }
 for (long long i = 3; i * i <= n; i += 2)
 {
  if (n % i == 0)
  {
   rez = rez / i * (i - 1);
   while (n % i == 0)
    n /= i;
  }
 }
 if (n != 1)
  rez = rez / n * (n - 1);
 return rez;
}

int main()
{
 in >> a >> n;
 return out << lgput(a, phi(n) - 1), 0;
}