#include <stdio.h>
#define lli long long int

FILE *in, *out;
lli A, MODULO;

void euclid(lli a, lli b, lli *x, lli *y)
{
    lli xa, ya;
    if(b == 0)
    {
        *x = a;
        *y = 0;
    }
    else
    {
        euclid(b, a%b, &xa, &ya);
        *x = ya % MODULO;
        *y = (xa - ya * (a / b)) % MODULO;
    }
}

int main()
{
    in = fopen("inversmodular.in", "r");
    out = fopen("inversmodular.out", "w");
    
    lli x, y;
    fscanf(in, "%lld %lld", &A, &MODULO);
    euclid(A, MODULO, &x, &y);
    fprintf(out, "%lld\n", (MODULO + x) % MODULO);

    fclose(in);
    fclose(out);
    return 0;
}