#include<cstdio>

using namespace std;

typedef long long int LL;

LL N,A;

LL phi(LL X)
{
    LL rasp=X,i;
    for(i=2;i*i<=X;i++)
        if(X%i==0)
        {
            while(X%i==0)
                X/=i;
            rasp=rasp/i*(i-1);
        }
    if(X>1) rasp=rasp/X*(X-1);
    return rasp;
}

LL exp(LL B,LL E)
{
    LL i,p=B,rasp=1;
    for(i=1; i<=E; i<<=1)
    {
        if(i&E) rasp=(rasp*p)%N;
        p=(p*p)%N;
    }
    return rasp;
}

int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);

    scanf("%lld%lld",&A,&N);

    printf("%lld\n",exp(A,phi(N)-1));

    return 0;
}