# include <fstream.h>
ifstream f ("inversmodular.in");
ofstream g ("inversmodular.out");
int a,b,c,m[3][3],mm[3][3],k,i,x,y,n,q,r;

  


 void euclid ()
 {
	 k=0;
	 while (b)
	 {
	 q=a/b;
	 r=a%b;
	 a=b;
	 b=r;
	 mm[1][1]=m[1][1];
	 mm[1][2]=m[1][2];
	 mm[2][1]=m[2][1];
	 mm[2][2]=m[2][2];
	 
	 m[1][1]=mm[1][1]*q+mm[1][2];
	 m[1][2]=mm[1][1];
	 m[2][1]=mm[2][1]*q+mm[2][2];
	 m[2][2]=mm[2][1];
	 k++;
	 }
 }

int main ()
{
	m[1][1]=1;
	m[2][2]=1;
	f>>a>>b;
	n=b;
		euclid ();
		if (k%2==0)
		{
			x=m[2][2];
			y=-m[1][2];
		}
		else
		{
			x=-m[2][2];
			y=m[1][2];
		}
		while (x<0)
			x=x+n;
		g<<x;
	
	return 0;
}