#include <fstream>
#include <cassert>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long N,P;
inline int gcd(int A, int B, int &X, int &Y)
{
    if (B == 0)
    {
        X = 1;
        Y = 0;
        return A;
    }

    int D, X0, Y0;
    D = gcd(B, A % B, X0, Y0);
    // X0 * B + Y0 * (A - (A / B) * B)
    // X0 * B + Y0 * A - Y0 * B * (A / B)

    X = Y0;
    Y = X0 - Y0 * (A / B);
    return D;
}

int main()
{


    int N, P;
    f>>N>>P;
   // assert(1 <= P && P <= 2000000000);
   // assert(1 <= N && N <= P - 1);
    int D, X, Y;
    D = gcd(N, P, X, Y);

    // N * X + P * Y == 1
    // N * X == 1 (mod P)

    if (X < 0)
        X += P;
        g<<X;
  //  printf("%d\n", X);

    return 0;
}