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

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

}

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;
}