#include<cstdio>
long long A,N;
long long phi(long long n)
{
    long long prod=n;
    for(long long i=2;(long long)i*i<=n;++i)
        if(n%i==0)
        {
            prod/=i;
            prod*=(i-1);
            while(n%i==0)
                n/=i;
        }
    if(n!=1)
    {
        prod/=n;
        prod*=(n-1);
    }
    return prod;
}
long long putlog(long long n,int p)
{
    long long pp,a;
    pp=1;
    a=n;
    while(p)
    {
        if(p&1)
        {
            pp*=a;
            pp%=N;
        }
        a*=a;
        a%=N;
        p>>=1;
    }
    return pp;
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%lld%lld",&A,&N);
    printf("%lld",putlog(A,phi(N)-1));
    return 0;
}