#include <fstream>
using namespace std;

int A, N, x, y;

void euclid(int a, int b)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return ;
    }

    euclid(b, a % b);
    int dx = x, dy = y;
    x = dy;
    y = dx + (a / b) * dy;
}

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

    f >> A >> N;
    euclid(A, N);
    x %= N;
    if (x < 0)
        x = x + N;

    g << x << '\n';
    g.close();
    return 0;
}