#include <fstream>

using namespace std;

long long int ans,i,N,A,expon;

long long phi(long long int a)
{
    long long aux=a;

    for(i=2;i*i<=a;i++)
    {
        if(a%i==0)
        {
        while(a%i==0)
            a=a/i;
        aux=(aux/i)*(i-1);
        }
    }

    if(a!=1)
        aux=(aux/a)*(a-1);

    return aux;
}


long long int putere(long long int baza, long long int exponent)
{
    long long int sol=1;
    for(;exponent;exponent>>=1)
    {
        if((exponent&1)==1)
            sol=(1LL*baza*sol)%N;
        baza=(1LL*baza*baza)%N;
    }
    return sol;
}

int main()
{
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");

    f>>A>>N;

    expon=phi(N)-1;

    ans=putere(A,expon);

    g<<ans;
}