#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int cmmdc(long long a, long long b, long long &x, long long &y)
{
    if(!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    long long x0, y0;
    /// x * a + y * b = d
    /// x0 * b + y0 * (a - a/b*b) = d
    /// x = y0;
    /// y = x0 - y0 * a/b
    int d = cmmdc(b, a % b, x0, y0);
    x = y0;
    y = x0 - a/b * y0;
    return d;
}

int main()
{
    long long x, y, a, n;
    fin >> a >> n;
    cmmdc(a, n, x, y);
    fout << ((x % n) + n) % n;
}