#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;
    for(d=2;d*d<=n;d++)
       if (n%d==0)
        {
            while(n%d==0)n/=d;
            sol= (sol/d)*(d-1);
        }
        if (n!=1) sol=sol/n*(n-1);
return sol;
}
LL  putere(LL  n,LL  p,LL 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;
    p=phi_n(n)-1;
    fo<<putere(a,p,n);
    return 0;
}