#include<fstream>
using namespace std;

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

int invers_modular(int nr, int mod)
{
	int x, y;
	
	euclid(nr, mod, x, y);
	while(x < 0)
        x += mod;

	return x;
}

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;
}