#include <fstream>
using namespace std;

void euclid(int a, int b, int *x, int *y);

int main() {
    int a, b, x, y;
    ifstream in("inversmodular.in");
    in >> a >> b;
    euclid(b, a, &y, &x);
    in.close();
    ofstream out("inversmodular.out");
    out << x;
    out.close();
    return 0;
}

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