#include<fstream.h>
ifstream F("inversmodular.in");
ofstream g("inversmodular.out");
long long x,y;
int A,B;
void f(long long &x, long long &y, int A, int B)
{if(B==0) {x=1;y=0;}
  else { f(x,y,B,A%B);
	  long long z=x;x=y;y=z-y*(A/B);
  }
}
int main()
{ F>>A>>B;
  f(x,y,A,B);
  if(x<=0) x=B+x%B;
  g<<x<<'\n';
 F.close();g.close();
return 0; 
	
}