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