#include<fstream>
#include<algorithm>

using namespace std;
typedef int64_t var;

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

typedef pair<var, var> Sol;
#define mp make_pair

Sol euclid(var a, var b, var c) {

    if(b == 0) {
        if(c % a)
            return mp(0, 0);
        else
            return mp(c/a, 0);
    } else {
        Sol rez = euclid(b, a%b, c);
        return mp(rez.second, rez.first - a/b * rez.second);
    }
}


int main() {
    var a, p;
    fin>>a>>p;

    auto R = euclid(a, p, 1);
    var r = R.first;
    fout<<r%p;
}