#include <cstdio>
#define LL long long
using namespace std;
int numprimes(int n)
{
    int ans=n;
    bool ok = false;
    int div = 2;
    while(div*div<=n)
    {
         ok=false;
        while(n%div==0)
        {
            n/=div;
            ok=true;
        }
        if(ok)
        {
            ans/=div;
            ans*=(div-1);
        }
        ++div;
    }
    if(n>1)
        ans=ans/n*(n-1);
    return ans;
}
LL pow(LL base, LL exp, LL mod)
{
    if(exp==0)
        return 1;
    else
    {
        int aux = pow(base,exp/2,mod);
        if(exp&1)
            return aux*aux%mod*base%mod;
        else
            return aux*aux%mod;
    }

}
LL iv(LL a, LL b)
{
    return pow(a,numprimes(b)-1,b);
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    LL a,n;
    scanf("%lld%lld",&a,&n);
    printf("%lld\n",iv(a,n));
    return 0;
}