#include <cstdio>
using namespace std;
FILE *in,*out;
long long phi(long long n)
{
long long d = 2,c = n,nr = 1;
while(d*d <= c)
{
if(c % d == 0)
{
while(c % d == 0)
c /= d;
nr = (n/d) * (d-1);
}
d ++ ;
}
if(c != 1)
{
nr = nr / c * (c-1);
}
return nr;
}
long long exp(long long n ,int p,long long modulo)
{
long long rez = 1;
while(p != 0)
{
if(p % 2 == 1)
rez = (rez*n) % modulo;
n = (n*n) % modulo;
p /= 2;
}
return rez;
}
int main()
{
in = fopen("inversmodular.in","r");
out = fopen("inversmodular.out","w");
long long a,n;
fscanf(in,"%lld %lld",&a,&n);
long long f = phi(n);
fprintf(out,"%lld",exp(a,f-1,n));
return 0;
}