#include <fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int a,n;
int putere(int a,int e)
{ int p=1;
  while(e>0)
  { if(e%2==0)
       a*=a,a%=n,e/=2;
    else
       p*=a,p%=n,e--;
  }
  return p;
}
int phi(int x)
{ int p=1;
  for(int i=2;i*i<=x;i++)
  { if(x%i!=0)
       continue;
    int e=0,k=1;
    while(x%i==0)
        x/=i,e++,k*=i;
    k/=i;
    p=(i-1)*k;
  }
  if(x!=1)
     p*=(x-1);
  return p;
}
int main()
{ in>>a>>n;
  out<<putere(a,phi(n)-1);
  in.close();
  out.close();
  return 0;
}