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