#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>

int phi(int N) {
	int x = N, i;
	for (i = 2; i * i <= N; ++i) {
		if (N % i == 0) {
			while (N % i == 0)
				N /= i;
			// Options
			x -= x / i; // 1
			//x = (x / i) * (i - 1); //2
		}
	}

	// Options
	if (N > 1) // 1
		x -= x / N;

	//if (N != 1) //2
		//x = x / N * (N - 1);

	return x;
}

int main()
{
	FILE *inversmodular_in, *inversmodular_out;
	int A, N, exp, res, i;

	inversmodular_in = fopen("inversmodular.in", "r");
	inversmodular_out = fopen("inversmodular.out", "w");

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

	exp = phi(N) - 1;
	res = 1;

	for (i = 1; i <= exp; i <<= 1) {
		if (i & exp)
			res = (res * A) % N;
		A = (A * A) % N;
	}

	fprintf(inversmodular_out, "%d\n", res); 

	fclose(inversmodular_in);
	fclose(inversmodular_out);

	return 0;
}