#include <cstdio>
FILE *f=fopen("inversmodular.in","r");
FILE *g=fopen("inversmodular.out","w");
long long mod;

long long phi(long long N)
{
    long long rez = N;
    for(long long  i = 2;i * i <= N; ++i)
    {
        if (N%i==0)
        {
            while(N%i==0)N/=i;
            rez=(rez / i) * (i - 1);
        }
    }
        if (N != 1) rez = rez / N * (N - 1);
    return rez;
}
long long invers(long long a,long long N)
{
    long long x1=a,x2=1;
    if(N==1)return a;
    while(N>1)
        if(N%2){x2=(x2*x1)%mod;N--;}
        else {x2=(x2*x2)%mod;N/=2;}
    return (x1*x2)%mod;

}
int main()
{
    long long a,N,put;
    fscanf(f,"%lld%lld",&a,&N);mod=N;
    put=phi(N);
    fprintf(g,"%lld",invers(a,put-1));
    return 0;
}