#include <bits/stdc++.h>

#define llg long long

llg A, N;

void Euclid(llg A, llg B, llg &X, llg &Y) {
    if (B == 0) {
        X = 1;
        Y = 0;
        return;
    }   Euclid(B, A%B, X, Y);

    llg Temp = Y;
    Y = X - (A/B)*Y;
    X = Temp;
}

std::ifstream In("inversmodular.in");
std::ofstream Out("inversmodular.out");

void Citire() {
    In >> A >> N;
}

void Rezolvare() {
    llg Aux, Inv;
    Euclid(A, N, Inv, Aux);

    if (Inv <= 0) Inv = Inv + Inv%N;
    Out << Inv << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}