#include <cstdio>
typedef long long l;
using namespace std;
l x,n;
l phi(l n)
{
	l a=n;
	for(l i=2;i*i<=n&&n>1;i++)
		if(n%i==0)
		{
			while(n%i==0&&n>1)
				n=n/i;
			a=(a/i)*(i-1);
		}
	if(n!=1)
		a=(a/n)*(n-1);
	return a;
}
l rid(l power)
{
	l aux=x%n,ans=1;
	while(power)
	{
		if(power%2==1)
			ans=(ans*aux)%n;
		aux=(aux*aux)%n;
		power/=2;
	}
	return ans;
}
int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%lld%lld",&x,&n);
	printf("%lld\n",rid(phi(n)-1));
	return 0;
}