#include <fstream>

using namespace std;

unsigned long long exp_log(unsigned long long x, int n, unsigned mod)
{
	if (n < 0) return exp_log((float)1 / x, -n, mod);
	if (n == 0) return 1;
	x = x % mod;
	if (n % 2 == 0) return exp_log(x * x, n / 2, mod) % mod;
	if (n % 2 != 0) return (x * exp_log(x * x, n / 2, mod) % mod) % mod;
}

unsigned phi(unsigned n)
{
	unsigned result = n;
	for (unsigned i = 2; i * i <= n; i++)
		if (n % i == 0)
		{
			while (n % i == 0) n /= i;
			result -= result / i;
		}
	if (n > 1) result -= result / n;
	return result;
}

int main()
{
	ifstream fin("inversmodular.in");
	ofstream fout("inversmodular.out");
	unsigned A, N, x;

	fin >> A >> N;
	x = exp_log(A, phi(N) - 1, N);
	fout << x;

	fin.close(); fout.close();
	return 0;
}