using namespace std;
# include <cstdio>

struct V
{
	int a, b, mod;
	V operator+ (const V &other)
	{
		V res;
		res.a = (this->a + other.a) % mod;
		res.b = (this->b + other.b) % mod;
		return res;
	}
	V operator- (const V &other)
	{
		V res;
		res.a = (this->a - other.a) % mod;
		res.b = (this->b - other.b) % mod;
		return res;
	}
	V operator* (const int other)
	{
		V res;
		res.a = (this->a * other) % mod;
		res.b = (this->b * other) % mod;
		return res;
	}
};

int Invers_Modular(int a, int b)
{
	int sol, q, r;
	V Va, Vb, Vr;
	Va.mod = Vb.mod = Vr.mod = b;

	Va.a = Vb.b = 1;
	Va.b = Vb.a = 0;

	while (b)
	{
		q = a / b;
		r = a % b;
		Vr = Va - Vb * q;
		a = b, Va = Vb;
		b = r, Vb = Vr;
	}
	sol = Va.a;

	return sol;
}

int main()
{
	int A, N, invA;
	FILE *inFile, *outFile;
	const char *inFileName = "inversmodular.in";
	const char *outFileName = "inversmodular.out";

	inFile = fopen(inFileName, "r");
	fscanf(inFile, "%d%d", &A, &N);
	fclose(inFile);

	invA = Invers_Modular(A % N, N);

	outFile = fopen(outFileName, "w");
	fprintf(outFile, "%d\n", invA);
	fclose(outFile);

	return 0;
}