#include<cstdio>

using namespace std;

typedef long long int lld;

void Read(),Print();

lld A,N;

lld ExpLog(lld B,lld E)
{
    if(E == 0) return 1LL;
    if(E == 1) return B%N;
    lld t = ExpLog(B,E/2);
    return ((t * t)%N * ExpLog(B,E%2))%N;
}

lld Phi(lld X)
{
    lld p,ans = X;
    for(p = 2; p * p <= X; p++)
        if(X%p == 0)
        {
            ans = ans / p * (p - 1);
            while(X%p == 0) X /= p;
        }
    if(X > 1) ans = ans / X * (X - 1);
    return ans;
}

int main()
{
    Read();
    Print();

    return 0;
}

void Read()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);

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

void Print()
{
    printf("%lld\n",ExpLog(A,Phi(N) - 1));
}