#include <bits/stdc++.h>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

// a * x + b * y = d
void euclid(int64_t a, int64_t b, int64_t& d, int64_t& x, int64_t& y) {
	if(b == 0) {
		d = a;
		x = 1;
		y = 0;
	} else {
		int64_t x0, y0;
		euclid(b, a % b, d, x0, y0);
		x = y0;
		y = x0 - (a / b) * y0;
	}
}
// ( x / y ) % mod = ( x * invmod(y,mod) ) % mod

int64_t invmod(int64_t n, int64_t k) {
	int64_t d, x, y;
	euclid(n, k, d, x, y);
	return (x + k) % k;
}

signed main() {
	int64_t x, y;
	fin >> x >> y;
	fout << invmod(x, y);
	return 0;
}