#include <fstream>
 
using namespace std;

ifstream fi("inversmodular.in");
ofstream fo("inversmodular.out");

long long int x, y, d;

void modular(long long int a, long long int b, long long int& x, long long int& y, long long int& d)
{
    if (b == 0)
    {
        a = d;
        x = 1;
        y = 0;
        return;
    }
    long long int x1, y1, q = a / b;
    modular(b, a%b, x1, y1, d);
    x = y1;
    y = x1 - y1*q;
}
 
int main()
{
    long long int A, N, X;
    fi >> A;
	fi >> N;
    modular(A, N, x, y, d);
    if (x < 0)
    {
        while (x < 0)
            x += N;
    }
    fo << x;
    return 0;
}