#include <fstream>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
long long a,x;
long long phi(long long n)
{
    long long b=n;
    long long d=2;long long  t=n;
    while(d*d<=b)
    {int p=0;
    while(b%d==0)
    {
        p++;
        b=b/d;
    }
    if(p!=0)
    {
        t=t/d*(d-1);
    }

d++;
    }
    if(b>1)t=t/b*(b-1);
    return t;
}
long long put(long long n,long long A)
{long long p=1;
    while(n>0)
    {
        if(n%2==1)p=p*A%x;
        A=A*A%x;
        n=n/2;
    }
    return p;
}
long long inv(long long n,long long k)
{
return put(n,phi(k)-1);
}
int main()
{

   fin>>a>>x;
   fout<<inv(a,x);
    return 0;
}