#include<cstdio>

int euler(int n)//calc ind lui euler pt n
{
	int p=n;
	for(int i=2;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 explog(int a,int e,int n)//calc a la e mod n (logaritmic)
{
	int p=1;
	while(e)
	{
		if(e&1)
			p=p*a%n;
		a=a*a%n;
		e>>=1;
	}
	return p;
}

int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	int a,n,e;
	scanf("%d%d",&a,&n);
	e=euler(n)-1;
	printf("%d\n",explog(a,e,n));
	return 0;
}