#include <stdio.h>
#include <stdlib.h>

int N = 0, A = 0;

int Putere(int A, int n)
{
	int P = 1;
	while (n)
	{
		if (n % 2 == 1)
			P = (P * A) % N;
		A = (A * A) % N;
		n /= 2;
	}
	return P;
}


int phi(int n)
{
	int result = n;
	for (int 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()
{
	FILE* f = fopen("inversmodular.in", "r"), * g = fopen("inversmodular.out", "w");
	int valoare_functiei_phi = 0, rezultat = 0;

	fscanf(f, "%d", &A);
	fscanf(f, "%d", &N);

	valoare_functiei_phi = phi(N);

	rezultat = Putere(A, valoare_functiei_phi - 1) % N;
	fprintf(g, "%d", rezultat);

	fclose(f);
	fclose(g);

	return 0;
}