#include <fstream>

using namespace std;

ifstream f ("inversmodular.in");
ofstream g ("inversmodular.out");

int a, M, r0, r1, x0, x1, q, r, x;

int main()
{
    f >> a >> M;

    r0 = a;
    r1 = M;
    x0 = 1;
    x1 = 0;

    while (r1 != 0)
    {
        r = r0 % r1;
        q = r0 / r1;
        x = x0 - q * x1;
        x0 = x1;
        x1 = x;
        r0 = r1;
        r1 = r;
    }

    if (x0 < 0) x0 += M;

    g << x0 << '\n';
    return 0;
}