#include <cstdio>

using namespace std;

int n, MOD;

void citire()
{
	scanf("%d %d", &n, &MOD);
}

void euclidExtins(int a, int b, int &x, int &y)
{
	if(b == 0)
	{
		x = 1;
		y = 0;
	}
	else
	{
		euclidExtins(b, a % b, x, y);

		int tmp = x;
		x = y;
		y = tmp - (a / b) * y;
	}
}

void solve()
{
	int x, y;
	euclidExtins(MOD, n, x, y);

	while(y < 0)
	{
		y += MOD;
	}

	printf("%d", y);
}

int main()
{
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);

	citire();
	solve();

	return 0;
}