#include<fstream>
using namespace std;
 
void euclid(int a, int b, int &x, int &y)
{
    if(!b)
    {
        x = 1;
        y = 0;
		return;
    }
	int x0, y0;
	euclid(b, a % b, x0, y0);
	y = x0 - (a / b) * y0;
	x = y0;
}
 
int invers_modular(int a, int b)
{
    int b0 = b, t, q;
	int x0 = 0, x1 = 1;
	if (b == 1) return 1;
	while (a > 1) {
		q = a / b;
		t = b, b = a % b, a = 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;
}