def modular_inverse(a, mod):
    """ Compute modular inverse using Extended Euclidean algorithm """
    r_prev, u_prev, v_prev, r, u, v = a, 1, 0, mod, 0, 1
    while r != 0:
        q = r_prev // r
        r_prev, u_prev, v_prev, r, u, v = (
            r,
            u,
            v,
            r_prev - q * r,
            u_prev - q * u,
            v_prev - q * v,
        )
    return u_prev