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