#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

int64_t exeuclid(int64_t a, int64_t b, int64_t *x, int64_t *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    int64_t x1, y1;
    int64_t g = exeuclid(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return g;
}

int64_t modinv(int64_t a, int64_t n) {
    int64_t x, y;
    int64_t g = exeuclid(a, n, &x, &y);
    if (g != 1) return -1;
    int64_t inv = x % n;
    if (inv < 0) inv += n;
    return inv;
}

int main() {
    int64_t a, n;
    FILE *input = fopen("inversmodular.in", "r");
    FILE *output = fopen("inversmodular.out", "w");
    if (!input || !output) {
        fprintf(stderr, "Eroare deschidere fisiere!");
        exit(-1);
    }
    if (fscanf(input, "%lld %lld", &a, &n) != 2) {
        fprintf(stderr, "Eroare la citire a si n!\n");
        exit(-1);
    }
    int64_t inv = modinv(a, n);
    fprintf(output, "%lld", inv);
    fclose(input);
    fclose(output);
    return 0;
}