#include <cstdio>

using namespace std;

long long mod;

void inversModular (long long a, long long n, long long &x, long long &y) {
	long long c, xx, yy;
	if (a == 0) {
		x = 0; y = 1;
		return;
	}
	inversModular (n % a, a, xx, yy);
	y = xx;
	x = (yy - xx * (n / a)) % mod;
	if (x < 0) {
		x += mod;
	}
}

int main () {
	long long a, n, x, y;
	freopen ("inversmodular.in", "rt", stdin);
	freopen ("inversmodular.out", "wt", stdout);
	scanf ("%lld%lld", &a, &n);
	mod = n;
	for (int i = 0; i < 50000; ++ i)
		inversModular (a % n, n, x, y);	
	printf ("%d\n", x);
	return 0;
}