#include <cstdio>

struct eulerEc
{
	long long int a;
	long long int b;
	long long int x;
	long long int y;
	long long int d;
};

eulerEc* euler(long long a, long long b)
{
	eulerEc* e;
	if (!b)
	{
		e = new eulerEc;
		e->a = a;
		e->b = b;
		e->x = 1;
		e->y = 0;
		e->d = a;

	} else {
		e = euler(b, a%b);
		e->a = a;
		e->b = b;
		long long aux = e->x;
		e->x = e->y;
		e->y = aux - (a/b)*e->y;
	}
	return e;
}

int main()
{
	FILE *fin = fopen("inversmodular.in", "r");
	FILE *fout = fopen("inversmodular.out", "w");
	long long int a;
	long long int n;
	fscanf(fin, "%lld%lld", &a, &n);

	eulerEc * e = euler(a, n);
	long long x = e->x % n;
	while (x < 0) x+=n;
	fprintf(fout, "%lld\n", e->x % n);
	delete e;
	fclose(fin);
	fclose(fout);
	return 0;
}