#include <cstdio>

int phi(int n)
{
	int rez=n,n2=n;
	
	for(int 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;
}

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

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