#include <fstream>

using namespace std;

const char InFile[]="inversmodular.in";
const char OutFile[]="inversmodular.out";

ifstream fin(InFile);
ofstream fout(OutFile);

int A,N,d,t;
long long x,y;

void gcd(int A, int B, long long &x, long long &y)
{
	if(B==0)
	{
		x=1;
		y=0;
		return;
	}
	gcd(B,A%B,x,y);
	t=x;
	x=y;
	y=t-y*(A/B);
}

int main()
{
	fin>>A>>N;
	fin.close();

	gcd(A,N,x,y);
	fout<<x;
	fout.close();
	return 0;
}