#include<stdio.h>

int A,N,X,Y;

int euclid(int A,int B,int &X,int &Y)
{
	if(B == 0)
	{
		X = 1; Y = 0;
		return A;
	}
	int D = euclid(B,A%B,X,Y);
	int C = X; X = Y; Y = C-(A/B)*Y;
	return D;
}

int main()
{
	FILE *f = fopen("inversmodular.in","r");
	FILE *g = fopen("inversmodular.out","w");
	
	fscanf(f,"%d %d",&A,&N);
	euclid(A,N,X,Y);
	fprintf(g,"%d",X%N);
	
	fclose(g);
	fclose(f);
	return 0;
}