#include <fstream>
#include <cmath>
using namespace std;
ifstream fi ("inversmodular.in");
ofstream fo ("inversmodular.out");
long long prim[200],x,y,phi,i;
long long rez;
int ph(int a)
{
  int sol,n=0;
  sol=a;
  for (i=2;i<=sqrt(a+.1);i++)
  if (a%i==0)
  {
    n++;
    prim[n]=i;
    while (a%i==0) a=a/i;
  }
  if (a>1) {n++;prim[n]=a;}
  for (i=1;i<=n;i++) sol=sol*(prim[i]-1)/prim[i];
  return sol;
}
long long inmult(long long baza,long long exponent)
{
  while (exponent>0)
  {
    if (exponent%2==1)
      {
        rez=(rez*baza)%y;
        exponent--;
      }
    else
      {
        baza=(baza*baza)%y;
        exponent=exponent/2;
      }
  }
  return rez%y;
}
int main()
{
    fi>>x>>y;
    phi=ph(y);
//    fo<<phi<<'\n';
    rez=1;
    fo<<inmult(x,phi-1);
    return 0;
}