#include <stdio.h>

void inv_modular(int a, int b, int *x, int *y) {
    if(!b) {
        *x = *y = 1;
        return;
    }

    int x1, y1;
    inv_modular(b, a%b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
}

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

    fscanf(in, "%d %d", &A, &N);
    fclose(in);

    int x, y;
    inv_modular(A, N, &x, &y);

    while(x < 0) {
        x += N;
    }

    printf("%d", x);
    // fprintf(out, "%d", x);
    fclose(out);

    return 0;
}