#include <fstream>

using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
long long a,n;
long long lgput(long long b,long long p,long long mod)
{
    long long sol;
    sol=1;
    while(p>0)
    {
        if(p%2==1)
            sol=(sol*b)%mod;
        b=(b*b)%mod;
        p/=2;
    }
    return sol;
}
long long getphi(long long n)
{
    long long phi=1,d,p;
    for(d=2;d*d<=n;d++)
    {
        if(n%d==0)
        {
            p=0;
            while(n%d==0)
            {
                n/=d;p++;
            }
            phi*=(d-1)*lgput(d,p-1,99999999999);
        }
    }
    if(n!=1) phi*=(n-1);
}
int main()
{
    cin>>a>>n;
    cout<<lgput(a,getphi(n)-1,n);
    return 0;
}