#include<fstream.h>
void euclid(int a,int b,int &x,int &y)
{if(!b)
 {x = 1;
  y = 0;}
 else
 {int x0, y0;
  euclid(b,a%b,x0,y0);
  x=y0;
  y=x0-(a/b)*y0;
 }
}
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int main()
{int A,N,x,y;
f>>A>>N;
euclid(A,N,x,y);
while(x<0)x+=N;
g<<x;
return 0;
}