#include <cstdio>

using namespace std;

int main()
{
    freopen ("inversmodular.in", "r", stdin);
    freopen ("inversmodular.out", "w", stdout);

    int a, b;
    scanf ("%d %d", &b, &a);

    int y0 = 0, y = 1, ca = a;
    while (b)
    {
        int c = a / b;
        int r = a % b;
        int cb = b;
        b = r;
        a = cb;

        int cy = y;
        y = y0 - c * y;
        y0 = cy;
    }

    y0 = (int)((1LL * (y0 % ca) + 1LL * ca) % (1LL * ca));
    printf ("%d\n", y0);

    return 0;
}