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

int A, N;

void cmmdc(long long *x, long long *y, int a, int b)
{
    if (!b)
    {
        *x = 1;
        *y = 0;
    }
    else
    {
        cmmdc(x, y, b, a % b);
        long long aux = *x;
        *x = *y;
        *y = aux - (*y) * (a / b);
    }
}

int main()
{
    long long inv = 0, ins = 0; 
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    scanf("%d %d", &A, &N);
    cmmdc(&inv, &ins, A, N);
    inv = (inv % N + N) % N;
    printf("%lld\n", inv);
    return 0;
}