def _extended_gcd(a, b):
    """Returns (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
    x, x_old, y, y_old = 0, 1, 1, 0
    while a != 0:
        (q, a), b = divmod(b, a), a
        y, y_old = y_old, y - q * y_old
        x, x_old = x_old, x - q * x_old
    return b, x, y