#include <cstdio>
#define LL long long

LL phi(LL n)
{
	LL rez=n,n2=n;
	
	for(LL i=2;i*i<=n2;i++)
		if(n%i==0)
		{
			while(n%i==0)
				n=n/i;
			rez=rez/i*(i-1);
		}
	
	if(n>1)
		return rez/n*(n-1);
	return rez;
}

LL ridicare(LL a,LL put,LL n)
{
	LL rez=1;
	while(put)
	{
		if(put%2==1)
			rez=(rez*a)%n;
		a=(a*a)%n;
		put>>=1;
	}
	
	return rez;
}

int main()
{
	LL a,n,x;
	LL put;
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%lld%lld",&a,&n);
	
	put=phi(n)-1;
	x=ridicare(a,put,n);
	
	printf("%lld",x);
	
	return 0;
}