#include<fstream>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long long A, n, fi;

long long putere(long long nr)
{
	long long z;
	if (nr==0) return 1;
	if (nr==1) return A%n;
	if (nr%2) return (A*putere(nr-1))%n;
	if (!(nr%2))
	{
		z=putere(nr/2)%n;
		return (z*z)%n;
	}
}

long long calculeaza_fi(long long x)
{
	long long d=2, aux=x, fi=x;
	while (aux>1 && d*d<=x)
		if ((aux%d))d++;
		else
		{
			while (!(aux%d)) aux/=d;
			fi=(fi/d)*(d-1);
		}
	if (aux>1) fi=(fi/aux)*(aux-1);
	return fi;
}

int main()
{
	f>>A>>n;
	fi=calculeaza_fi(n);
	g<<putere(fi-1)<<"\n";
	f.close();
	g.close();
	return 0;
}