#include <fstream>
using namespace std;

void extended_gcd(long long a, long long b, long long &gcd, long long &x, long long &y) {
    long long old_r = a, r = b;
    long long old_s = 1, s = 0;
    long long old_t = 0, t = 1;

    while (r != 0) {
        long long quotient = old_r / r;
        long long temp = r;
        r = old_r - quotient * r;
        old_r = temp;

        temp = s;
        s = old_s - quotient * s;
        old_s = temp;

        temp = t;
        t = old_t - quotient * t;
        old_t = temp;
    }

    gcd = old_r;
    x = old_s;
    y = old_t;
}

int main() {
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");

    long long A, N;
    fin >> A >> N;

    long long gcd, x, y;
    extended_gcd(A, N, gcd, x, y);

    long long X = (x % N + N) % N;

    fout << X << endl;

    fin.close();
    fout.close();
    return 0;
}