#include<fstream> 
using namespace std; 
int A,N,x,y;
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);//d=i,i=r;     
   x=y0;
   y=x0-(a/b)*y0;
  } 
}   
int main()//A^x % N ==1
{
  ifstream f("inversmodular.in"); ofstream g("inversmodular.out");
	f>>A>>N;
	euclid(A,N,x,y);
	while(x<0)
	  x+=N;
	g<<x;
 return 0;
 f.close();g.close();
}