#include <bits/stdc++.h>
#warning sunt pe onlinegdb

using namespace std;

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

long long euclid(long long n, long long m, long long &x, long long &y) {
    if (m == 0) {
        x = 1;
        y = 0;
        return n;
    }
    long long x0, y0, ret = euclid(m, n % m, x0, y0);
    x = y0;
    y = x0 - x * (n / m);
    return ret;
}

int main() {
    long long n, m;
    fin >> n >> m;
    long long x, y;
    assert(euclid(n, m, x, y) == 1);
    fout << x << '\n';
    return 0;
}