#include<fstream>
#define LL long long
using namespace  std;
ifstream fi("inversmodular.in");
ofstream fo("inversmodular.out");
LL a,n,p;
LL phi_n(LL n)    //se cal. phi(n) indicatorul Euler pt.n
{
    LL sol=n,d;  // sol- rezultatul phi(n)
    for(d=2;d*d<=n;d++) //iau toti divizorii d
       if (n%d==0)      //d este doar prim(se descompune n in factori primi)
        {
            while(n%d==0)n/=d;
            sol=(sol/d)*(d-1); //aplic calculul formulei Euler
        }
        if (n!=1) sol=sol/n*(n-1);//daca ramane un div. prim >sqrt(n) ex:2*13???
return sol;
}
LL  putere(LL  n,LL  p,LL MOD)//calculez logarirmic (n^p)%MOD
{
    LL r;
    if (p==0) return 1;
    else
       if (p%2==0){r=putere(n,p/2,MOD)%MOD;return(r*r)%MOD;}
       else  return (putere(n,p-1,MOD)*n)%MOD;
}
int main()
{
    fi>>a>>n;
    fo<<putere(a,phi_n(n)-1,n);//inversul modular (a^(phi(n)-1))%n
    return 0;
}