#include <fstream>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

pair<long long, long long> euclid_extins(int a, int b) {
    if (!b)
        return {1, 0};
    auto p = euclid_extins(b, a % b);
    return {p.second, p.first - (a / b) * p.second};
}

int main() {
    int a, n;
    f>>a>>n;
    int rez = euclid_extins(a, n).first % n;
    while (rez < 0)
        rez += n;
    g<<rez;
    return 0;
}