#include <fstream>
using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int A, B, i = 1;
int x, y;

int V[][2] = {1, 0, 0, 1, 0, 0};

void GCD(int A, int B){
	if (B == 0) return;
	else {
		i++;
		V[i % 3][0] = V[(i - 2) % 3][0] - (A / B)*V[(i - 1) % 3][0];
		V[i % 3][1] = V[(i - 2) % 3][1] - (A / B)*V[(i - 1) % 3][1];
		return GCD(B, A%B);
	}
}

int main(){

	fin >> A >> B;

	GCD(B, A);

	fout << (V[(i-1) % 3][1] + B) % B;

	return 0;
}