class Polynomial:
    def __init__(self, coef, mod):
        self.mod = mod
        self.coef = [c % mod for c in coef[:]]
        while len(self.coef) > 1 and self.coef[0] == 0:
            self.coef.pop(0)        
        self.deg = len(self.coef) - 1
        

    def __str__(self):
        st = "".join(f"{('+' if i > 0 else '') if c > 0 else '-'}{str(abs(c)) if abs(c) != 1 else ''}x^{self.deg - i}" for i, c in enumerate(self.coef[:-2]))
        if self.deg > 0 and self.coef[-2] != 0:
            st += f"{('+' if self.deg > 1 else '') if self.coef[-2] >= 0 else '-'}{str(abs(self.coef[-2])) if abs(self.coef[-2]) != 1 else ''}x"
        if self.coef[-1] != 0 and self.deg > 0:
            st += f"{('+' if self.deg > 0 else '') if self.coef[-1] >= 0 else '-'}{str(abs(self.coef[-1])) if abs(self.coef[-1]) != 1 else '1'}"
        if self.deg == 0:
            st += str(self.coef[0])
        return st
        
    def __add__(self, other):
        deg = max(self.deg, other.deg)
        cs, os = self.coef[::-1], other.coef[::-1]
        add = [0] * (deg + 1)
        for i in range(deg + 1):
            add[i] = ((cs[i] if i < len(cs) else 0) + (os[i] if i < len(os) else 0)) % self.mod
        return Polynomial(add[::-1], self.mod)

    def __neg__(self):
        return Polynomial([(-c) % self.mod for c in self.coef], self.mod)

    def __sub__(self, other):
        return self + (-other)

    def __mul__(self, other):
        if isinstance(other, int):
            return Polynomial([(other * c) % self.mod for c in self.coef], self.mod)
        else:
            deg = self.deg + other.deg
            return Polynomial([sum((self.coef[i] if i < self.deg + 1 else 0) * (other.coef[k - i] if k - i < other.deg + 1 else 0) for i in range(k + 1)) % self.mod for k in range(deg + 1)], self.mod)

    def __rmul__(self, other):
        if isinstance(other, int):
            return Polynomial([(other * c) % self.mod for c in self.coef])
        else:
            deg = self.deg + other.deg
            return Polynomial([sum((self.coef[i] if i < self.deg + 1 else 0) * (other.coef[k - i] if k - i < other.deg + 1 else 0)for i in range(k + 1)) for k in range(deg + 1)])
    
    def __pow__(self, exp):
        assert isinstance(exp, int) and exp >= 0
        r = Polynomial([1], self.mod) 
        for _ in range(exp):
            r = r * self
        return r

    def __divmod__(self, other):
        q, r = Polynomial([0], self.mod), Polynomial(self.coef, self.mod)
        while (r.deg != 0 or r.coef[0] != 0) and r.deg >= other.deg:
            inv = pow(other.coef[0], -1, self.mod)
            c = r.coef[0] * inv
            t = Polynomial([c if i == 0 else 0 for i in range(r.deg - other.deg + 1)], self.mod)
            q = q + t
            r = r - t * other
        return (q, r)

def gcd(a, b, p):    
    A, B = Polynomial(a, p), Polynomial(b, p)
    while B.deg > 0:
        Q, R = divmod(A, B)
        A, B = B, R       
    return B

def extended_gcd(a, b, p):
    _r, r = Polynomial(a, p), Polynomial(b, p)
    _s, s = Polynomial([1], p), Polynomial([0], p)
    _t, t = Polynomial([0], p), Polynomial([1], p)
    while r.deg > 0 or r.coef[0] != 0:
        q, rem = divmod(_r, r)
        _r, r = r, _r - q * r
        _s, s = s, _s - q * s
        _t, t = t, _t - q * t
    c = pow(_r.coef[0], -1, p)
    _r *= c
    _s *= c
    _t *= c
    return (_r.coef, [] if _s.deg == 0 and _s.coef[0] == 0 else _s.coef,  [] if _t.deg == 0 and _t.coef[0] == 0 else _t.coef)
    
_n = [34, 45, 40, 0, 36]
_d = [116, 99, 66]
mod = 127
g, u, v = extended_gcd(_n, _d, mod)
print("g:", g, u, v)