#include <stdio.h>

int A, N, X, Y;

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


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