#include<cstdio>
int n;
int mod(int a, int m)
{
    return (a + m) % m;

}
void euclid_extins(int a, int b, int &d, int &x, int &y)
{
    if(b == 0)
    {
        d = a;
        x = 1;
        y = 0;
        return;
    }
    int xprim = 0, yprim = 0, q = a / b;
    euclid_extins(b,  a % b, d, xprim, yprim);
    x = yprim , n;
    y = xprim - yprim * q , n;
}


int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    int tests, a, b, c, rez1, rez2 , d;
    rez1 = rez2 = 0;
    scanf("%d%d", &a,&n);
    euclid_extins(a, n, d, rez1, rez2);
    printf("%d" , mod(rez1 , n));
return 0;
}