#include <stdio.h>

void euclid(long long a, long long b, long long *x, long long *y)
{
    if (b == 0)
    {
        *x = 1;
        *y = 0;
        return;
    }

    long long x1, y1;

    euclid(b, a % b, &x1, &y1);

    *x = y1;
    *y = x1 - (a / b) * y1;
}

int main()
{
    FILE *in, *out;

    long long A, N;
    long long X, Y;

    in = fopen("inversmodular.in", "r");
    out = fopen("inversmodular.out", "w");

    fscanf(in, "%lld %lld", &A, &N);

    euclid(A, N, &X, &Y);

    X = (X % N + N) % N;

    fprintf(out, "%lld\n", X);

    fclose(in);
    fclose(out);

    return 0;
}