#include<stdio.h>
long long a,n,t,M;
inline void totient()
{
	t=n;
	if(!(n&1))
	{
		t>>=1;
		while(!(n&1))
			n>>=1;
	}
	for(int i=3; i*i<=n; i+=2)
	{
		if(!(n%i))
		{
			t=t/i*(i-1);
			while(!(n%i))
				n/=i;
		}
	}
	if(n!=1)
		t=t/n*(n-1);
}
int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%lld%lld",&a,&n);
	M=n;
	totient();
	--t;
	long long rez=1;
	for(; t; t>>=1)
	{
		if(t&1)
			rez=(a*rez)%M;
		a=(a*a)%M;
	}
	printf("%lld\n",rez);
	return 0;
}