#include <fstream>
using namespace std;

long long modinv(long long a, long long n) {
    long long x0 = 1, x1 = 0;
    long long a0 = a, n0 = n;
    while (n0) {
        long long q = a0 / n0;
        long long t = a0 - q * n0;
        a0 = n0;
        n0 = t;
        t = x0 - q * x1;
        x0 = x1;
        x1 = t;
    }
    if (x0 < 0) x0 += n;
    return x0;
}

int main() {
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    long long a, n;
    fin >> a >> n;
    fout << modinv(a, n);
    return 0;
}