#include <fstream>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long a,n,b,k,ind,aux,p;
int main()
{int i,r=1;
f>>a>>n;
a=a%n;
ind=n;
aux=n;
for(i=2;i*i<=n;i++)
{   p=0;
    while(aux%i==0){aux=aux/i;p++;}
    if(p) ind=ind/i*(i-1);
}
if(aux>1) ind=ind/aux*(aux-1);
b=ind-1;
while(b)
{
        if(b%2==1) r=(r*a)%n;
a=(a*a)%n;
b=b/2;

}
g<<r;
    return 0;
}