#include <fstream>
#include <algorithm>

using namespace std;

int A, N;

int phi(int x)
{
	int result = x;
	for (int i = 2; i * i <= x; ++i)
		if (x % i == 0)
		{
			result = result / i * (i - 1);
			while (x % i == 0)
				 x /= i;
		}
	if (x != 1)
		result = result / x * (x - 1);
	
	return result;
}
int power(int x, int y, int MOD)
{
	if (y == 0) return 1;
	if (y & 1) return 1LL * x * power(x, y - 1, MOD) % MOD;
	return power(1LL * x * x % MOD, y / 2, MOD);
}

int main()
{
	ifstream fin("inversmodular.in");
	ofstream fout("inversmodular.out");
	
	fin >> A >> N;
	fout << power(A, phi(N) - 1, N) << '\n';
	
	fin.close();
	fout.close();
}