#include <fstream>
# define LL long long
using namespace std;
LL a,b, d,x,y;
 void Euclid_Extins( LL a, LL b, LL&x, LL&y, LL&d)
 {
     if (b==0){d=a; x=1;y=0;}
     else { LL x0, y0;
     Euclid_Extins(b, a%b, x0, y0, d);
     x=y0;
     y=x0-a/b*y0;
     }
 }

int main()
{ifstream f("inversmodular.in") ;
ofstream g("inversmodular.out") ;
f>>a>>b;
Euclid_Extins(a,b,x,y,d);
   /* if (x1 < 0) {
        LL q = (-x1) / b;
        x1 += q * n;
        if (x1 < 0)
            x1 += b;*/
    if (x<0) x+=b;
g<<x;

    return 0;
}