#include <bits/stdc++.h>

#define llg long long

llg A, N;

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

llg InvMod(llg A, llg MOD) {
    llg Temp, Inv;
    Euclid(A, MOD, Inv, Temp);
    return (Inv + MOD) % MOD;
}

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

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

void Rezolvare() {
    Out << InvMod(A, N);
}

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

    return 0;
}