#include<fstream>
#include<cmath>
using namespace std;
long int a,n;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int prim(int x)
{int d,ok=1;
if(x==2)
return 1;
else if(x%2==0)
return 0;
else
{for(d=3;d<=sqrt(x)&&ok;d+=2)
if(x%d==0)
ok=0;
return ok;
}
}
int psi(int y)
{int s=0;
for(int i=2;i<n;i++)
if(prim(i))
s++;
return s;
}
int main()
{f>>a>>n;
g<<(int)pow(a,psi(n)-1)%n;
return 0;
}