#include <stdio.h>

void cmmdc(long long a, long long b, long long * d, long long * x, long long * y)
{
	if (b==0)
	{
		*d = a;
		*x = 1;
		*y = 0;
	} else {
		long long x0,y0;
		cmmdc(b,a%b,d,&x0,&y0);
		*x = y0;
		*y = x0 - (a / b) * y0;
	}
}

long long moddiv(long long a, long long b, long long n)
{
	long long d,x,y;
	cmmdc(n,b,&d,&x,&y);
	if (a%d) return -1;
	if (y<0)
		y += ((-y)/n + 1)*n;
	y = y % n;
	return (y*a/d)%n;
}

int main (void)
{
	FILE * fin = fopen("inversmodular.in","r");
	long long n,a;
	fscanf(fin,"%lld%lld",&a,&n);
	fclose(fin);
	long long r = moddiv(1,a,n);
	FILE * fout = fopen("inversmodular.out","w");
	fprintf(fout,"%lld\n",r);
	fclose(fout);
	return 0;
}