#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 a=n;
    long long d=2;long long  t=n;
    while(d*d<=a)
    {int p=0;
    while(a%d==0)
    {
        p++;
        a=a/d;
    }
    if(p!=0)
    {
        t=t/d*(d-1);
    }

d++;
    }
    if(a>1)t=t/a*(a-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,k-1);
}
int main()
{

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