#include <cstdint>
#include <fstream>

using namespace std;

pair<int64_t, int64_t> Euclid(int64_t a, int64_t b) {
    if (b == 0) {
        return {1, 0};
    }

    auto p = Euclid(b, a % b);
    return {p.second, p.first - (a / b) * p.second};
}

int64_t ModInv(int64_t a, int64_t b) {
    auto inv = Euclid(a, b).first;
    while (inv < 0) {
        inv += b;
    }
    return inv;
}

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

    int64_t a, b;
    fin >> a >> b;

    fout << ModInv(a, b) << "\n";
    return 0;
}