#include <fstream>
#define ll long long
std::ifstream in("inversmodular.in");
std::ofstream out("inversmodular.out");

std::pair<ll, ll> ext(int a, int b) {
	if (!b) return { 1, 0 };
	auto p = ext(b, a % b);
	return { p.second, p.first - (a / b) * p.second };
}

int main() {
	int a, n;
	in >> a >> n;

	auto rez = ext(a, n).first;

	while (rez < 0) rez += n;
	out << rez;

	return 0;
}