#include <fstream>

using namespace std;

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

int a, n;

inline long long lgput(int x, int y)
{
	long long sol = 1;
	while (y)
	{
		if (y & 1)
			sol = (sol * x) % n;
		x = ((x % n) * (x % n)) % n;
		y >>= 1;
	}
	return sol;
}

inline bool prim(int a)
{
	int x = 2, y;
	while (x * x <= a)
	{
		if (a % x == 0)
			return 0;
		y = a / x;
		if (a % y == 0)
			return 0;
		++x;
	}
	if (x * x == a)
		return 0;
	return 1;
}

inline long long phi(int n)
{
	long long rez = 1;
	int d = 2;
	if (prim(n))
		return n - 1;
	while (n)
	{
		if (n % d == 0)
		{
			int p = 0;
			while (n % d == 0)
			{
				++p;
				n /= d;
			}
			rez *= (d - 1) * lgput(d, p - 1);
		}
		if (d * d <= n)
		{
			if (d == 2)
				++d;
			else
				d += 2;
		}
		else
			d = n;
	}
	return rez;
}

int main()
{
	in >> a >> n;
	return out << lgput(a, phi(n) - 1), 0;
}