#include<cstdio>

using namespace std;

int N,A;

int phi(int X)
{
    int 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;
}

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

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

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

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

    return 0;
}