#include <cstdio>

int A,N;

int LgPut(int X, int B)
{
    int A=1;
    while(B)
    {
        if(B%2) A=(1LL*A*X)%N;
        X=(1LL*X*X)%N;
        B/=2;
    }
    return A;
}

int main(){
    FILE* fin = fopen("inversmodular.in","r");
    FILE* fout = fopen("inversmodular.out","w");

    int i,X,phi;

    fscanf(fin,"%d %d",&A,&N);

    phi = (X = N);
    for(i = 2; 1LL * i * i <= N; ++i)
    if(X % i == 0)
    {
        phi = phi / i * (i-1);
        while(X % i == 0) X/=i;
    }
    if(X != 1) phi = phi / X * (X-1);
    if(phi == N) --phi;

    fprintf(fout,"%d\n",LgPut(A,phi-1));


return 0;
}