---

def gf128_inv(x):
    """
    Инверсия в GF(2^128) через расширенный алгоритм Евклида.
    Полином: x^128 + x^7 + x^2 + x + 1
    """
    if x == 0:
        raise ZeroDivisionError("0 не имеет обратного")
    
    # Полином MOD = x^128 + x^7 + x^2 + x + 1 = (1 << 128) | 0x87
    MOD = (1 << 128) | 0x87
    
    # Полиномиальные операции над GF(2)
    def poly_deg(a):
        return a.bit_length() - 1 if a else -1
    
    def poly_divmod(a, b):
        """Деление полиномов с остатком."""
        q = 0
        while a and poly_deg(a) >= poly_deg(b):
            shift = poly_deg(a) - poly_deg(b)
            q ^= (1 << shift)
            a ^= (b << shift)
        return q, a
    
    def poly_mul(a, b):
        """Умножение полиномов (без редукции)."""
        result = 0
        while b:
            if b & 1:
                result ^= a
            a <<= 1
            b >>= 1
        return result
    
    def poly_mod(a, m):
        """Приведение по модулю m."""
        while poly_deg(a) >= poly_deg(m):
            shift = poly_deg(a) - poly_deg(m)
            a ^= (m << shift)
        return a
    
    # Расширенный Евклид
    r0, r1 = MOD, x
    s0, s1 = 0, 1
    
    while r1 != 0:
        q, r = poly_divmod(r0, r1)
        r0, r1 = r1, r
        s0, s1 = s1, s0 ^ poly_mul(q, s1)
        # Приводим s0, s1 по модулю
        s0 = poly_mod(s0, MOD)
        s1 = poly_mod(s1, MOD)
    
    # r0 = gcd(MOD, x) = 1
    # s0 * x = r0 mod MOD = 1
    return s0 & MASK128