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

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;
}

FILE *file;

int main()
{
	int a, n;
	file = fopen("inversmodular.in", "r");
	fscanf(file, "%d", &a);
	fscanf(file, "%d", &n);
	fclose(file);

	int p = phi(n) - 1;
	long long power, sol = 1;

	// printf("phi %d\n", p);

	power = a;
	for (uint32_t i = 0; (1 << i) <= p; ++i)
	{
		if ((1 << i) & p)
			sol = (sol * power) % n;
		power = (power * power) % n;
	}

	file = fopen("inversmodular.out", "w");
	fprintf(file, "%lld\n", sol % n);
	fclose(file);

	return 0;
}