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