#include <stdio.h>

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

    long long x1, y1;
    long long cmmdc = euclid_extins(b, a % b, &x1, &y1);

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

    return cmmdc;
}

long long gaseste_invers_modular(long long A, long long N) {
    long long x, y;
    euclid_extins(A, N, &x, &y);

    long long invers = (x % N + N) % N;
    return invers;
}

int main() {
    FILE *fin = fopen("inversmodular.in", "r");
    FILE *fout = fopen("inversmodular.out", "w");

    if (fin == NULL || fout == NULL) {
        if (fin) fclose(fin);
        if (fout) fclose(fout);
        return 1;
    }

    long long A, N;

    if (fscanf(fin, "%lld %lld", &A, &N) != 2) {
        fclose(fin);
        fclose(fout);
        return 1;
    }

    long long raspuns = gaseste_invers_modular(A, N);

    fprintf(fout, "%lld\n", raspuns);

    fclose(fin);
    fclose(fout);

    return 0;
}