#include<stdio.h>
long long i, n, nr, put, a, rez;

void det_put()
{
	for (i=2;i*i<n;i++)
		if (n%i==0)
			nr++;
	nr*=2;
	if (n%i==0)
		nr++;
	put=n-1-nr;
}

long long putere(long long k)
{
	long long x;
	if (k==0)
		return 1;
	else
	{
		x=putere(k/2);
		if (k%2==0)
			return (x*x)%n;
		else
			return (((x*x)%n)*a)%n;
	}
}

int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%ld %ld",&a,&n);
	det_put();
	rez=putere(put-1);
	printf("%ld",rez);
	return 0;
}