#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int main()
{

long long int y0 = 0, y1 = 1, M, a, aux, r, c, y ;
fin>>a>>M;
aux = M;
while (a != 0)
{
 r = M % a;
c = M / a;
M = a;
a = r;
y = y0 - c * y1;
y0 = y1;
y1 = y;
}

while (y0 < 0)
{
y0 += aux;
}
fout << y0;
    return 0;
}