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

using namespace std;

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

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

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