#include <fstream>
using namespace std;

ifstream fi ("inversmodular.in");
ofstream fo ("inversmodular.out");
long long a, n, f, rasp;

long long lgput(int b, int e)
{
	int r = 1, cb = b;
	while (e)
	{
		if(e&1 == 1)
			r*=b;
		b*=b;
		e>>=1;
		r%=n;
		b%=n;
	}
	return r;
}

int main()
{
	fi >> a >> n;
	//cate nr mai mici decat n sunt prime cu el?
	f = n - 1;
	for (long long i = 2; i*i <= n; ++i)
		if (n*i == 0)
			if (i*i == n)
				--f;
			else
				f-=2;
	//ridicarea la f - 1
	rasp = lgput(a, f - 1);
	fo << rasp;
	return 0;
}