#include <stdio.h>
long xx, yy, n, q;

void calc(long a, long b, long &x, long &y)
{
	long x1, y1;
	if (b==0)
	{	x=1;	y=0;	}
	else
	{
		calc(b,a%b,x1,y1);
		x=y1;	y=x1-y1*(a/b);
	}
}

int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%ld %ld",&q,&n);
	calc(q,n,xx,yy);
	while (xx<1)
		xx+=n;
	while (xx>=n)
		xx-=n;
	printf("%ld",xx);
	return 0;
}