#include <fstream>

using namespace std;

void euclid(int a, int b, int &x, int &y)
{
    if(!b)
        x = 1, y = 0;
    else
    {
        int x0, y0;
        euclid(b, a % b, x0, y0);
        y = x0 - (a / b) * y0;
        x = y0;
    }
}

int main()
{
    ifstream in ("inversmodular.in");
    int A, N, X, Y;
    in >> A >> N;
    euclid(A, N, X, Y);
    while( X < 0 )
        X += N;

    ofstream out("inversmodular.out");
    out<< X << '\n';
    return 0;
}