#include <cstdio>
#include <cassert>

using namespace std;

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;
}

inline int isPrim(int N)
{
    if (N == 2)
        return 1;
    if (N % 2 == 0)
        return 0;

    for (int i = 3; i * i <= N; i += 2)
        if (N % i == 0)
            return 0;
    return 1;
}

int main()
{
    freopen("inversmodular.in", "rt", stdin);
    freopen("inversmodular.out", "wt", stdout);

    int N, P;
    scanf("%d %d", &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;
    printf("%d\n", X);

    return 0;
}