#include <fstream>

using namespace std;

int A, N;

void Euclid(int A, int B, int &X, int &Y) {
    if(!B) {
        X = 1;
        Y = 0;
        return;
    }
    int X0, Y0;
    Euclid(B, A % B, X0, Y0);
    X = Y0;
    Y = X0 - (A / B) * Y0;
}

int main() {
    ifstream in("inversmodular.in");
    in >> A >> N;
    in.close();

    int X, Y;
    Euclid(A, N, X, Y);
    X %= N;
    if(X < 0)
        X += N;
    ofstream out("inversmodular.out");
    out << X << "\n";
    out.close();
}