#include <stdio.h>
#define ll long long
int a,n;
inline int euler(int x)
{
	int i,rez=x;
	for (i=2; i*i<=x; i++)
		if (x % i==0)
		{
			rez=rez/i*(i-1);
			while (x % i==0) x/=i;
		}
	if (x!=1)
		rez=rez/x*(x-1);
	return rez;
}
inline int lgput(int nr,int exp)
{
	int rez=1,act=nr;
	while (exp)
	{
		if (exp & 1)
			rez=((ll)rez*act)%n;
		act=((ll)act*act)%n;
		exp>>=1;
	}
	return rez;
}
int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%d%d",&a,&n);
	printf("%d\n",lgput(a,euler(n)-1));
	return 0;
}