// Include
#include <fstream>
using namespace std;

// Definitii
#define ll long long

// Functii
void euclid(ll a, ll b, ll *x, ll *y);

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

ll num, mod;

// Main
int main()
{
	in >> num >> mod;
	ll x, y;
	euclid(num, mod, &x, &y);
	
	if(x < 0)
		x = (x % mod) + mod;
	
	out << x << '\n';
	
	in.close();
	out.close();
	return 0;
}

void euclid(ll a, ll b, ll *x, ll *y)
{
	if(!b)
	{
		*x = 1;
		*y = 0;
	}
	else
	{
		ll x0, y0;
		euclid(b, a%b, &x0, &y0);
		*x = y0;
		*y = x0 - (a/b) * y0;
	}
}