#include <bits/stdc++.h>

using namespace std;

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

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

int invmod(int n, int k) {
	int d, x, y;
	euclid(n, k, d, x, y);
	return (x + k) % k;
}

int main() {
	int x, y;
	fin >> x >> y;
	fout << invmod(x, y);
	return 0;
}