#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

int A,MOD;

int Extended_GCD(int A, int B, int &X, int &Y)
{
    if (B == 0)
    {
        X = 1;
        Y = 0;
        return A;
    }

    int X0, Y0, D;
    D = Extended_GCD(B, A % B, X0, Y0);
    X = Y0;
    Y = X0 - (A / B) * Y0;
    return D;
}

int Inv(int i)
{
    int inv,garbage;
    Extended_GCD(i, MOD, inv, garbage);
    inv %= MOD;
    while (inv < 0)
    {
        inv += MOD;
    }
    return inv;
}

int main()
{
    f >> A >> MOD;
    g << Inv(A);
    f.close();
    g.close();
    return 0;
}