#include <fstream>

long long modInv(long long a, long long b, long long & x, long long & y){
    if(a == 0){
        x = 0;
        y = 1;
        return b;
    }
    long long x1, y1, lnko = modInv(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return lnko;
}

int main(){
    std::ifstream bem("inversmodular.in");
    long long a, mod, x, y;
    bem >> a >> mod;
    bem.close();
    modInv(a, mod, x, y);
    std::ofstream kim("inversmodular.out");
    kim << x;
    kim.close();
    return 0;
}