#include <fstream>
using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");
long long phi(long long x)
{
    long long euler=x,f,p;
    f=2;
    while(f*f<=x)
    {
        p=0;
        while(x%f==0)
        {
            p++;
            x=x/f;
        }
        if(p>0)
            euler=euler/f*(f-1);
        f++;
    }
    if(x>1)
        euler=euler/x*(x-1);
    return euler;
}

long long fastpowmod(long long a,long long b,long long n)
{
    long long aa,p;
    aa=a;
    for(p=1;b;b=b>>1)
    {
        if(b&1)
            p=(p*aa)%n;
        aa=(aa*aa)%n;
    }
    return p;
}

long long invers_modular(long long A,long long N)
{
    return fastpowmod(A,phi(N)-1,N);
}

int main()
{
    long long A,N;
    fin>>A>>N;
    fout<<invers_modular(A,N);
    return 0;
}