#include<fstream>
#include<cmath>
using namespace std;
unsigned long long int a,n;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
unsigned long long int prim(unsigned long long int x)
{unsigned long long 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;
}
}
unsigned long long int psi(unsigned long long int y)
{unsigned long long int s=0;
for(unsigned long long 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;
}