#include<stdio.h>

struct Vect
{
long x, y;
};
void atr(Vect &V,Vect V1){
	V.x=V1.x;V.y=V1.y;
}
Vect prod(Vect V,long q){
	V.x*=q;V.y*=q; return V;
}
void dif(Vect &V,Vect V1,Vect V2)
{ V.x=V1.x-V2.x;V.y=V1.y-V2.y;
}
int main()
{
	Vect v,v1,v0;
	 long a,b,q,r,n;
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);

	scanf("%ld%ld",&b,&a);
	v0.x=v1.y=1;
	v0.y=v1.x=0;
	n=a;
	while(b)
	{
		q=a/b;
		r=a%b;
		a=b;
		b=r;
		atr(v,v0);
		atr(v0,v1);
		dif(v1,v,prod(v0,q));
	}
	
		printf("%ld\n",(v0.y+n)%n);

	return 0;
}