#include<fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long a,n,phi=1,i,b,r,p;
int main()
{
    f>>a>>n;
    p=n;
    for(i=2;i*i<=n;i++)
        if(n%i==0)
        {
            while(!(n%i)) {n/=i; phi*=i;}
            phi/=i; phi*=(i-1);
        }
    if(n>1) phi*=n-1;
    b=phi-1;
    r=1;
    for(i=1;i<=b;i<<=1)
    {
        if(i&b) r=(r*a)%p;
        a=(a*a)%p;
    }
    g<<r;
    return 0;
}