#include<stdio.h>
using namespace std;
long long nr,x,n,d,n1,r,phi,aux;
long long ridic(long long a1,long long b1)
{
	long long p2;
	p2=1;
	while(b1>0)
	{
		if(b1%2==0)
		{
		a1=(1LL*a1*a1)%r;
		b1=b1/2;
		}
		else
		{
		p2=(1LL*p2*a1)%r;
		b1--;
		}
	}
	return p2;
}
int main()
{
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);
scanf("%lld",&x);
scanf("%lld",&n);
n1=n;
aux=n;
d=1;
r=n;
phi=1;
while(d*d<=aux)
{
	d++;
	nr=0;
	while(aux%d==0)
	{
		aux=aux/d;
		nr++;
	}
	if(nr>0) phi=phi*ridic(d,nr-1)*(d-1);
}
if(aux!=1) phi=phi*(aux-1);
//printf("%d\n",phi);
printf("%lld\n",ridic(x,phi-1));
return 0;
}