#include <stdio.h>


void euclid_extins(long long a, long long b, long long *x, long long *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
    } else {
        long long x0, y0;
        euclid_extins(b, a % b, &x0, &y0);
        *x = y0;
        *y = x0 - (a / b) * y0;
    }
}

int main() {
    FILE *fin = fopen("inversmodular.in", "r");
    FILE *fout = fopen("inversmodular.out", "w");
    
    long long a, m, x, y;
    fscanf(fin, "%lld %lld", &a, &m);
    
    euclid_extins(a, m, &x, &y);
    
    x = (x % m + m) % m; 
    
    fprintf(fout, "%lld\n", x);
    
    fclose(fin);
    fclose(fout);
    return 0;
}