#include <iostream>
#include <fstream>
#define ll long long

using namespace std;

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

ll a, MOD, x, y;

ll euclidExtins(ll a, ll b)
{	if(!b)
		{	x = 1;
			y = 0;
			return a;
		}
	ll g = euclidExtins(b, a % b);
	ll x1 = y, y1 = x - y * (a / b);
	x = x1;
	y = y1;
	return g;
}

int main()
{
	fin >> a >> MOD;
	ll g = euclidExtins(a, MOD);
	while(x < 0)
		x += MOD;
	fout << x << '\n';
	return 0;
}