#include<iostream>
#include<fstream>

using namespace std;

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

int A, R, phi;

int Determina_phi(int R)
{
    int d, k, p;
    phi = R;
    /// din care scadem nr_divizori
    d=2; p=1;
    if (R%d == 0)
  {
    k = 0;
    while (R%d == 0)
    {
        k++;
        R = R/d;
    }
    p = p * (k+1);
  }
  d = 3;
  while (d*d <= R)
  {
      if (R%d == 0)
      {
          k = 0;
          while (R%d == 0)
          {
             k++;
             R = R/d;
          }
          p = p * (k+1);
      }

      d = d+2;
  }

  ///if (R != 1)
  ///  p = p * 2;

  phi = phi - p;
}

void Ridica_la_putere(int n)
{
    int p=1, x;
    x = A;
    while (n>0)
    {
        if (n%2==0)
        {
            n=n/2;
            x=x*x;
        }
        else
        {
            p=p*x;
            n--;
        }
    }
    fout << p%R << "\n";
}

int main ()
{
   fin >> A >> R;
   phi = Determina_phi(R);
   Ridica_la_putere(phi-1);
   fin.close();
   fout.close();
   return 0;
}