#include <fstream>
using namespace std;

ifstream in { "inversmodular.in" };
ofstream out { "inversmodular.out" };

void Euclid_extins(int64_t& x, int64_t& y, int64_t a, int64_t b) {
    if (!b) {
        x = 1;
        y = 0;
    } else {
        Euclid_extins(x, y, b, a % b);
        int64_t temp = x;
        x = y;
        y = temp - y * (a / b);
    }
}

int main() {
    int64_t a, mod;
    in >> a >> mod;
    
    int64_t sol, y;
    Euclid_extins(sol, y, a, mod);
    
    if (sol <= 0)
        sol = mod + sol % mod;
    
    out << sol;
}