#include <cstdio>

long long A, N;

long long find(long long x)
{
    long long rez = x;
    
    for(long long i = 2; i*i <= x; ++i)
        if(x % i == 0)
        {
            while(x % i == 0)
                x /= i;
            rez = (rez/i) * (i-1);
        }
        
    if(x > 1) rez = (rez/x)*(x-1);
    return rez - 1;
}

int main()
{
    freopen("inversmodular.in","rt",stdin);
    freopen("inversmodular.out","wt",stdout);

    scanf("%lld %lld",&A, &N);

    long long P = find(N), Rez = 1;

    for(;P; P >>= 1)
    {
        if(P & 1)
            Rez = (Rez * A) % N;
        A = (A * A) % N;
    }
    printf("%lld\n",Rez);
}