def inverse(a, n, strict = True):
    """
    Compute the inverse of a modulo n using the Extended Euclidean algorithm.

    If strict is True (default), raises an error if a is not invertible.
    Otherwise, a number b is output such that a*b % n == gcd(a, b).
    """
    b, x, y = n, 0, 1
    while a != 0:
        k = int(b // a)
        b, a, x, y = a, b - k*a, y, x - k*y
    if strict and b not in [-1, 1]:
        raise ValueError("input not invertible")
    return (b*x) % n