#include <fstream>
#include <iostream>
#include <string>
#include <queue>
#include <vector>

using namespace std;


const string file = "inversmodular";

const string infile = file + ".in";
const string outfile = file + ".out";



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

	}

}



int main()
{

	long long A;
	long long N;


	fstream fin(infile.c_str(), ios::in);

	fin >> A >> N;

	fin.close();


	long long x = 0;
	long long y = 0;

	euclid(A, N, x, y);

	while(x < 0)
		x += N;


	long long raspuns = x;

	fstream fout(outfile.c_str(), ios::out);
	fout << raspuns << "\n";
	fout.close();

}