#include <fstream>
using namespace std;

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

void modul(long long a, long long n, long long &x, long long &y) {
	if (n == 0) {
		x = 1;
		y = 0;
		return;
	}
	long long x_, y_, q = a / n;
	modul(n, a % n, x_, y_);
	x = y_;
	y = x_ - q * y_;
}

int main() {
	long long a, n, x, y;
	fin >> a >> n;
	modul(a, n, x, y);
	fout << (x % n + n) % n;
}