#import<fstream>
int64_t a,b,x,y,z=1,r,c,d;main(){std::ifstream{"inversmodular.in"}>>a>>b;d=b;while(a)r=b%a,c=b/a,b=a,a=r,x=y-c*z,y=z,z=x;while(y<0)y+=d;std::ofstream{"inversmodular.out"}<<y;}