#include <fstream.h>

struct v {
    int x, y;

} V[3];

int A, N, M, I;

void read() {

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

}

void solve() {

    V[0].x = V[1].y = 1;
    V[0].y = V[1].x = 0;
    int i, r, q;

    M = N;
    i = 2;
    r = N % A;
    q = N / A;

    while (r > 0) {

        V[i].x = V[(i + 1) % 3].x - q * V[(i + 2) % 3].x;
        V[i].y = V[(i + 1) % 3].y - q * V[(i + 2) % 3].y;

        N = A;
        A = r;
        r = N % A;
        q = N / A;
        
        i = (i + 1) % 3;

    }

    I = (M + V[(i + 2) % 3].y) % M;

}

void write() {

    ofstream fout("inversmodular.out");
    fout << I << '\n';
    fout.close();

}

int main() {

    read();
    solve();
    write();

    return 0;
}