#include <iostream>
#include <fstream>
#include <tuple>

using namespace std;

// Funcția care implementează Algoritmul lui Euclid extins
tuple<long long, long long, long long> extended_gcd(long long a, long long b) {
    if (b == 0) {
        return {a, 1, 0};
    }
    auto [gcd, x1, y1] = extended_gcd(b, a % b);
    return {gcd, y1, x1 - (a / b) * y1};
}

int main() {
    ifstream infile("inversmodular.in");
    ofstream outfile("inversmodular.out");

    if (!infile || !outfile) {
        cerr << "Error opening file" << endl;
        return 1;
    }

    long long A, N;
    infile >> A >> N;

    auto [gcd, x, y] = extended_gcd(A, N);

    if (gcd != 1) {
        outfile << "Nu exista invers modular" << endl;
    } else {
        // Asigurăm că x este pozitiv
        x = (x % N + N) % N;
        outfile << x << endl;
    }

    infile.close();
    outfile.close();

    return 0;
}