#include <bits/stdc++.h>

using namespace std;

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

long long A, N, inv;

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

long long inversModular(const long long A)
{
    long long 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;
}