#include <fstream>

using namespace std;

int A, N;
long long Inv;

void cmmdc(int a, int b, long long & x, long long & y) {

    if(b == 0) {
        x = 1;
        y = 0;
    } else {

        cmmdc(b, a % b, x, y);

        int tmp = x;
        x = y;
        y = tmp - (a / b) * y;

    }

}
void Solve() {

    long long y; // y cries because he/she is only used to find x

    cmmdc(A, N, Inv, y);

    Inv %= N;
    if(Inv < 0)
        Inv += N;

}
void Read() {

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

}
void Write() {

    ofstream out("euclid2.out");
    out << Inv << '\n';
    out.close();

}
int main() {

    Read();
    Solve();
    Write();

    return 0;

}