#include <algorithm>
#include <fstream>
using namespace std;

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

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

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