#include <stdio.h>

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

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

    long long a, n;
    if (fscanf(fin, "%lld %lld", &a, &n) == 2) {
        long long x0 = 1, x1 = 0;
        long long b0 = a, b1 = n;

        while (b1 != 0) {
            long long q = b0 / b1;
            long long tmpr = b0 % b1;
            b0 = b1;
            b1 = tmpr;

            long long tmpx = x0 - q * x1;
            x0 = x1;
            x1 = tmpx;
        }

        while (x0 < 0) {
            x0 += n;
        }
        x0 %= n;

        fprintf(fout, "%lld\n", x0);
    }

    fclose(fin);
    fclose(fout);
    return 0;
}