#include <fstream>

using namespace std;

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

int A, MOD;

void gcd(int a, int b, int& X, int& Y)
{
    if (b == 0)
    {
        X = 1;
        Y = 0;
        return;
    }

    int X0, Y0;
    gcd(b, a % b, X0, Y0);

    X = Y0;
    Y = X0 - (a / b) * Y0;
}

int main()
{
    fin >> A >> MOD;

    int X, Y;
    gcd(A, MOD, X, Y);

    int inv = X % MOD;
    while (inv < 0)
        inv += MOD;

    fout << inv << '\n';

    fin.close();
    fout.close();
    return 0;
}