#include <fstream>
#include <bitset>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int i,v[22500],put,j,l;
bitset <50001> viz;
long long a,n;
long long ridicare(int put)
{
  long long y,pr;
  if (put==1)
     return a;
  else
  {
    y=ridicare(put/2);
    pr=(((y%n)*(y%n))%n);
    if (put%2==1) pr=(pr*a)%n;
    return pr;
  }
}
int main()
{
    f>>a>>n;
    v[++l]=2;
    for (i=3;i<=45000;i+=2)
      if (viz[i]==false)
    {
      v[++l]=i;
      j=i*i;
      if (j/i==i)
         for (j=i*i;j<=45000;j+=i)
         viz[j]=true;
    }
    put=1;
    for (i=1;i<=l && v[i]*v[i]<=n;i++)
      if (n%v[i]==0)
    {
      put*=(v[i]-1);
      n=n/v[i];
      while(n%v[i]==0)
        put*=v[i],n/=v[i];
    }
    if (n>1)
      put*=(n-1);
    put--;
    g<<ridicare(put)<<'\n';
    return 0;
}