#include <fstream>
#include <tuple>

using namespace std;

#define inFile "inversmodular.in"
#define outFile "inversmodular.out"

ifstream in(inFile);
ofstream out(outFile);

tuple < int, int, int > gcd(int a, int b) {
    if(b == 0) return make_tuple(a, 1, 0);
    tuple < int, int, int > gcdNext = gcd(b, a%b);
    return make_tuple(get<0>(gcdNext),
                      get<2>(gcdNext),
                      get<1>(gcdNext) - (a / b) * get<2>(gcdNext));
}

int main() {
    int a, p, modInv;

    in >> a >> p;
    modInv = get<1>(gcd(a, p));
    if(modInv < 0) modInv = p + modInv % p;

    out << modInv << "\n";
    return 0;
}