#include <fstream>
#include <cmath>
 
using namespace std;
 
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
 
int a, n;
 
int main() {
    fin >> a >> n;
    int y0 = 0, y1 = 1, aux = n;
    while(a != 0) {
        int r = n % a, c = n / a;
        n = a;
        a = r;
        int y = y0 - c * y1;
        y0 = y1;
        y1 = y;
    }
    while(y0 < 0) {
        y0 += aux;
    }
    fout << y0;
	return 0;
}