#include <bits/stdc++.h>

#define int long long

using namespace std;

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

int n, m;

void invMod(int &x, int &y, int a, int b) {
    if(b == 0) {
        x = 1; y = 0;
    }
    else {
        invMod(x, y, b, a % b);
        int aux = x;
        x = y;
        y = aux - y * (a / b);
    }
}

signed main() {
    in >> n >> m;

    int inv = 0, ins;

    invMod(inv, ins, n, m);

    if(inv <= 0) {
        inv = m + inv % m;
    }

    out << inv << '\n';

    return 0;
}