#include<cstdio>
int a,fu;
int phi(int n)
{
	int p=n;
	for(int 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(int n,int p)
{
	int 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("%d%d",&a,&fu);
	printf("%d",pog(a,phi(fu)-1));
	return 0;
}