---

def gf128_inv(x):
    """Инверсия в GF(2^128) через EGCD с разворотом битов."""
    if x == 0:
        raise ZeroDivisionError
    
    # Разворачиваем биты: GCM-представление -> обычное (little-endian)
    def rev(y):
        r = 0
        for i in range(128):
            if (y >> i) & 1:
                r |= (1 << (127 - i))
        return r
    
    x_le = rev(x)
    MOD = (1 << 128) | 0x87  # x^128 + x^7 + x^2 + x + 1
    
    def deg(a):
        return a.bit_length() - 1 if a else -1
    
    def divmod_poly(a, b):
        q = 0
        while a and deg(a) >= deg(b):
            s = deg(a) - deg(b)
            q ^= (1 << s)
            a ^= (b << s)
        return q, a
    
    def mul_poly(a, b):
        r = 0
        while b:
            if b & 1:
                r ^= a
            a <<= 1
            b >>= 1
        return r
    
    def mod_poly(a, m):
        while a and deg(a) >= deg(m):
            s = deg(a) - deg(m)
            a ^= (m << s)
        return a
    
    r0, r1 = MOD, x_le
    s0, s1 = 0, 1
    while r1:
        q, r = divmod_poly(r0, r1)
        r0, r1 = r1, r
        s0, s1 = s1, s0 ^ mod_poly(mul_poly(q, s1), MOD)
    
    # s0 * x_le = 1 mod MOD
    return rev(s0 & MASK128)