#include<cstdio>
long long nr,a,n;
long long phi(long long n)
{
	long long p=n,d,e;
	d=2;
	for(d=2;d*d<n;d++)
	{
		e=0;
		while(n%d==0)
		{
			e++;
			n=n/d;
		}
		if(e!=0)
		{p=p/d; p=p*(d-1);}
	}
	if(n>1)
		{p=p/n; p=p*(n-1);}
	return p;
}
long long putlog(long long a, long long p)
{
	long long pp;
	pp=1;
	while(p)
	{
		if(p&1)
		{
			pp*=a;
			pp=pp%n;
		}
		a=a*a;
		pp=pp%n;
		p>>=1;
	}
	return pp;
}
int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%lld%lld",&a,&n);
	nr=phi(n);
	printf("%lld",putlog(a,nr-1));
	return 0;
}