#include<cstdio>
#include<cstdlib>
#include<cmath>

long long a,n;

long long nrprime(long long nr)
{
    long long phi=nr;
    long long fact;
    int radical;
    radical=sqrt(nr);
    for(fact=2; fact<=radical; fact++)
    {
        if(nr%fact==0)
        {
            while(nr%fact==0)
                nr=nr/fact;
            phi=(phi/fact)*(fact-1);
        }
    }
    if(nr!=1)
        phi=(phi/nr)*(nr - 1);
    return phi;
}

long long power(long long nr, long long p, long long n)
{
    if(p==0)
        return 1;
    else if(p==1)
        return nr%n;
    else if(p%2==0)
        return power(nr*nr, p/2, n)%n;
    else if(p%2==1)
        return (nr*power(nr*nr, (p-1)/2, n))%n;
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%lld %lld",&a,&n);
    long long p, inversmod;
    p=nrprime(n) - 1;
    inversmod=power(a, p, n);
    printf("%lld\n",inversmod);
    return 0;
}