#include <bits/stdc++.h>

using namespace std;

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

int A, N, inv;

void euclidExtins(const int a, const int b, int& x1, int& y1)
{
    if (b == 0)
    {
        x1 = 1;
        y1 = 1;
        return;
    }
    
    int x2, y2;
    euclidExtins(b, a % b, x2, y2);
    
    x1 = y2;
    y1 = (x2 - a / b * y2 + N) % N;
}

int inversModular(const int A)
{
    int x1, y1;
    euclidExtins(A, N, x1, y1);
    return x1;
}

int main()
{
    f >> A >> N;
    inv = inversModular(A);
    while (inv < 0)
        inv += N;
    g << inv << "\n";
    
    f.close();
    g.close();
    return 0;
}