#include <fstream>

using namespace std;

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

int a, n;

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-1);
          rez /= i;
       }
   }

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

int Inv_Mod (int n, int mod)
{
   int p = phi(mod) - 1;
   int rez = 1;

    while (p)
    {
        if (p % 2 == 1)
            rez = (1LL * rez * n) % mod;
        n = (1LL * n * n) % mod;
        p /= 2;
    }

  return rez;
}

int main()
{
  f >> a >> n;
  g << Inv_Mod(a, n);
    return 0;
}