#include <fstream>

using namespace std;
ifstream f("inversmodular.in"); ofstream g("inversmodular.out");

int x, y,d,a,b;
void euclid_extins( int a, int b, int &x, int &y, int &d)
{ int xo, yo;
    if (b==0){d=a;y=0;x=1;}
    else {euclid_extins(b, a%b, xo, yo,d);
    x=yo;
    y=xo-a/b*yo;
    }

}
int main()
{f>>a>>b;euclid_extins(a,b, x,y, d);
g<<x;

    return 0;
}