#include <fstream>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
long long lg_put(long long base, long long exp, long long mod)
{
   long long p =1;
   while(exp>0)
   {
       if(exp&1)
           p = (p*(base%mod))%mod;
      base = ((base%mod) * (base%mod))%mod;
      exp = exp >>1;
   }
   return p;
}
///Stim din Theorema lui Euler ca (x^(phi(n)-1))%n este inversul modular a lui x.In cazul in care n este prim, atunci phi(n) = n-1.
///Mai mult phin(n) semnifica nr de nr prime cu n, mai mici decat n.
///phi(n) = n * (f1-1)/f1*(f2-1)/f2*...*(fk-1)/fk, unde n = f1^p1*f2^p2*....*fk^pk
///Daca exponentul este prim atunci solutia va fi base^(exp-2).
long long phi(long long n)
{
   long long phi = n, d =2, e;
   while(d*d<=n and d >1)
   {
       e =0;
       while(n%d==0)
       {
          n = n/d;
          e++;
       }
       if(e>0)
           phi = phi/d*(d-1);
       d++;
   }
   if(n>1)
    phi = phi/n*(n-1);
  return phi;
}
int main()
{
    long long n, m;
    fin>>n>>m;
    fout<<lg_put(n, phi(m)-1, m)<<"\n";
    return 0;
}