#include<stdio.h>
#include<math.h>
FILE *f=fopen("inversmodular.in","r"), *g=fopen("inversmodular.out","w");

int A, N, FI, N2;


void CalculareFI(){
int radN, i;

    N2 = N;

    radN = sqrt(N);
    FI = N;

    for(i=2;i<=radN;i++)
        if(N%i==0){

            while( N%i==0 )
                N/=i;

            FI = (FI / i) * (i-1);

        }

    if( N != 1 )
        FI = ( FI / N ) * ( N-1 );

    N = N2;

}

int rptl( int aa, int bb, int cc ){
long long int a, b, c, r=1;

    a = 1LL * aa;
    b = 1LL * bb;
    c = 1LL * cc;

    while( b > 0 ){

        if( b % 2 == 1 )
            r = (r * a) % c;

            a = (a * a) % c;

        b/=2;

    }
    return ((int)r);
}

int main(){

    fscanf(f,"%d %d\n",&A,&N);

    CalculareFI();

    fprintf(g,"%d\n",rptl(A,FI-1,N));

return 0;
}