#include <fstream>

using namespace std;

ifstream f ("inversmodular.in");
ofstream g ("inversmodular.out");

long long A, N;

pair<long long, pair<long long, long long> > extendedEuclid(long long a, long long b) {
    if(a == 0) return make_pair(b, make_pair(0, 1));
    pair<long long, pair<long long, long long> > p;
    p = extendedEuclid(b % a, a);
    return make_pair(p.first, make_pair(p.second.second - p.second.first*(b/a), p.second.first));
}

long long modInverse(long long a, long long m) {
    return (extendedEuclid(a,m).second.first + m) % m;
}

int main() {
    f >> A >> N;
    g << modInverse(A, N);
    return 0;
}