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

void inv_mod(long long a, long long b, long long *x, long long *y) 
{
    if (b == 0) 
    {
        *x = 1;
        *y = 0;
        return;
    }
    long long x1, y1;
    inv_mod(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
}

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