#include <fstream>

using namespace std;
ofstream fout("inversmodular.out");

int a, n;
int exp_rapida(int a, int phi);

int main()
{
	freopen("inversmodular.in", "r", stdin);
	scanf("%d%d", &a, &n);
	int d = 2;
	int cn = n;
	int phi = n - 1;
	for (int i = 2; i*i <= n; i++)
		if (!(n%i))
		{
			phi -= phi / i;
			while (!(n%i)) n /= i;
		}
	if (n>1) phi -= phi / n;
	n = cn;
	fout << exp_rapida(a, phi - 1) << '\n';
	return 0;
}

int exp_rapida(int a, int phi)
{
	int ans = 1;
	int pw = a;
	for (int i = 1; i <= phi; i <<= 1)
	{
		if (i & phi)
			ans = (ans * pw) % n;
		pw *= pw;
		pw %= n;
	}
	return ans;
}