#include <bits/stdc++.h>

int main() {
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);

	int a, n;

	int mat[2][3]{};
	scanf("%d %d", &a, &n);
	mat[0][0] = a;
	mat[1][0] = n;
	mat[0][1] = mat[1][2] = 1;


	while (mat[0][0] * mat[1][0]) {
		int r = mat[0][0] < mat[1][0];
		int c = mat[r][0] / mat[!r][0];
		for (int j = 0; j < 3; j++)
			mat[r][j] -= c * mat[!r][j];
	}

	int result = mat[0][0] ? mat[0][1] : mat[1][1];
	while (result < 0)
		result += n;

	printf("%d\n", result);

	return 0;
}