#include<fstream>
#define ull unsigned long long
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
ull a,n;
ull lgnp(ull n, ull p, ull mod)
{
    ull r=1;
    while(p)
    {
        if(p%2==1) r=(1LL*r*n)%mod;
        n=(n*n*1LL)%mod;
        p/=2;
    }
    return r;
}
ull phi(ull n)
{
    ull d=2,fm,nr=1;
    do
    {
        fm=0;
        while(n%d==0)
        {
            n/=d;
            fm++;
        }
        if(fm>0)
            nr=nr*(d-1)*lgnp(d,fm-1,n);
        d++;
        if(d*d>n&&n>1)
        {
            nr=nr*(n-1);
            n=1;
        }
    }
    while(n>1);
    return nr;
}
using namespace std;
int main()
{
    fin>>a>>n;
    fout<<lgnp(a,phi(n)-1,n)%n;
    return 0;
}