#include <bits/stdc++.h>
 
 using namespace std;
 
 int main() {

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

	int n, mod;
	in >> n >> mod;

	function<void(long long&, long long&, int, int)> extended_gcd = [&](long long &x, long long &y, int a, int b) {
		if(!b) {
			x = 1; y = 0;
		} else {
			extended_gcd(x, y, b, a%b);
			long long aux = x;
			x = y;
			y = aux - 1LL * y * (a / b);
		}
	};

	long long inv = 0, ins = 0;
	extended_gcd(inv, ins, n, mod);

	if(inv <= 0) {
		inv = n + inv % n;
	}

	out << inv << '\n';

	return 0;
 }