#include <fstream>
#define LL long long
using namespace std;
ifstream fi("inversmodular.in");
ofstream fo("inversmodular.out");

LL a,n;

LL getPhi(LL x)
{
    LL rez=x,aux=x;
    for (int i=2; 1LL*i*i<=aux; i++)
    {
        if (x%i==0)
        {
            rez=(rez*(i-1))/i;
            while (x%i==0)
                x/=i;
        }
    }
    if (x!=1)
        rez=(rez*(x-1))/x;
    return rez;
}

LL logExp(LL b,LL e,LL M)
{
    /// calculeaza (b^e)%M
    LL rez=1,p=5;
    for (int i=0; (e>>i)>0; i++)
    {
        if ((e>>i)&1)
        {
            rez=(rez*p)%M;
        }
        p=(p*p)%M;
    }
    return rez;
}

int main()
{
    fi>>a>>n;
    LL phi=getPhi(n);
    //fo<<phi;

    /// rezultatul este: (a^(phi-1))%n
    LL ans=logExp(a,phi-1,n);
    fo<<ans;
    return 0;
}