#include<fstream>
using namespace std;
  
int invers_modular(int nr, int mod)
{
    int b0 = mod, t, q, x0 = 0, x1 = 1;
	if(mod == 1)
		return 1;
	while(nr > 1)
	{
		q = nr / mod;
		t = mod;
		mod = nr % mod;
		nr = t;
		t = x0;
		x0 = x1 - q * x0;
		x1 = t;
	}
	if(x1 < 0)
		x1 += b0;
	return x1;
}
 
int main()
{
    int A, N;
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
     
    f >> A >> N;
    g << invers_modular(A, N);
 
    f.close();
    g.close();
     
    return 0;
}