#include<iostream>
#include<fstream>

using namespace std;

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

long long int k, a, P;

int Phi(int n)
{
    int w = n;
    int d=2;

    if (n % d == 0)
    {
        w /= d;
        w *= (d-1);
        while (n%d == 0)
        n = n/d;
    }

    d = 3;

    while (n!=1 && d*d <= n)
    {
      if (n%d == 0)
      { w /= d;
        w *= (d-1);
      while (n%d == 0)
       n = n/d;
      }
      d=d+2;
   }
    if (n!=1)
    { w /= n;
	 w *= (n-1);
    }
    return w;
}

 /// n =    1011010111
 ///  1 = 0000000001
 /// n & (1) = 1  daca n = impar
 /// n & (1) = 0  daca n = par

void Ridicare_Putere(long long int x, long long int k)
{
    /// x^n = x ^ (n/2) * x ^ (n/2) , daca n = par
    /// x^n=  x * x ^ (n-1),             daca n = impar

    int p = 1;

    while (k > 0)
    {
        if (k % 2 == 1) /// if (n & 1 == 1)
        {
            k--;
            p = ((p%P) * (x%P)) % P;
        }

        else /// n % 2 == 0
        {
            k = k/2;   /// n << 1;
            x  = ((x%P) * (x%P)) % P;
        }
    }

    fout << p << "\n";
}

int main ()
{
   fin >> a >> P;
   k = Phi(P);
   /// calculare a ^ (k-1) % P
   k--;

   Ridicare_Putere(a, k); /// imi calculeaza x ^ k % P
   fin.close();
   fout.close();
   return 0;
}