#include <stdio.h>

void extended_euclidean_algorithm(int a, int b, int *x, int *y)
{
	if (b == 0)
	{
		*x = 1;
		*y = 0;
		return;
	}

	int x1, y1;
	extended_euclidean_algorithm(b, a % b, &x1, &y1);

	*x = y1;
	*y = x1 - (a / b) * y1;
}

FILE *file;

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

	int x, y;
	extended_euclidean_algorithm(a, n, &x, &y);

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

	return 0;
}