#include<cstdio>

void double_assign(int *pl1, int *pl2,    int r1, int r2)
{
    *pl1 = r1;
    *pl2 = r2;
}

int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    int A, N;
    scanf("%d %d", &A, &N);

    //euclid
    int a=A, b=N;
    int prevx=1, prevy=0, x=0, y=1;
    while (b!=0)
    {
        int cat = a/b;
        double_assign(&prevx,&x,   x,prevx-cat*x);
        double_assign(&prevy,&y,   y,prevy-cat*y);
        double_assign(&a,&b,   b,a%b);
    }
    int inv=prevx;
    if (inv<=0)
        inv+=N;
    printf("%d", inv);
    return 0;
}