# coding: utf-8
    
class Zp:
    def __init__(self, x, p):
        self.__p = p
        self.__x = x % p
    def __repr__(self):
        return "{} (mod {})".format(self.__x, self.__p)
    def __neg__(self):
        return self.__class__((-self.__x)%self.__p, self.__p)
    def __add__(self, other):
        if self.__p != other.__p:
            raise ValueError("Eléments de corps différents.")
        return self.__class__((self.__x + other.__x) % self.__p, self.__p)
    def __sub__(self, other):
        return self + (-other)
    def __mul__(self, other):
        if self.__p != other.__p:
            raise ValueError("Eléments de corps différents.")
        return self.__class__((self.__x * other.__x) % self.__p, self.__p)
    def __pow__(self, n):
        return self.__class__(pow(self.__x, n, self.__p), self.__p)
    def __eq__(self, other):
        return self.__p == other.__p and self.__x == other.__x
    def inverse(self):
        if self.__x == 0:
            raise ZeroDivisionError("0 n'est pas inversible !")
        r0 = self.__p
        r1 = self.__x
        u0 = v1 = 1
        u1 = v0 = 0
        while r1 > 1:
            q = r0 // r1
            r0, r1 = r1, r0 - q * r1
            u0, u1 = u1, u0 - q * u1
            v0, v1 = v1, v0 - q * v1
        return self.__class__(v1 % self.__p, self.__p)
    def __truediv__(self, other):
        return self * other.inverse()
    def modulus(self):
        return self.__p
    def est_nul(self):
        return self.__x == 0

def FacteursPremiers(N):
    L = [] if N%2 == 1 else [2]
    while N&1 == 0: N >>= 1
    k = 3
    while N > 1:
        if N%k == 0:
            L.append(k)
            while N%k == 0: N //= k
        else:
            k += 2
    return L

def Generateur(p):
    if p == 2: return Zp(1,2)
    F = FacteursPremiers(p-1)
    for w in range(2, p):
        ok = True
        for f in F:
            if pow(w,(p-1)//f,p) == 1:
                ok = False
                break
        if ok: return Zp(w,p)
    raise ValueError(f"aucun générateur de Z/{p}Z trouvé...")

def RacinePrimitive(n, p):
    if (p-1) % n != 0: 
        raise ValueError(f"Pas de racine {n}-ème modulo {p}")
    
    return Generateur(p)**((p-1)//n)

def Poly(coeffs, p):
    return [Zp(c, p) for c in coeffs]

def Addition(F, G):
    if len(F) == 0: return G
    if len(G) == 0: return F
    p = F[0].modulus()
    assert p == G[0].modulus(), "les polynômes sont définis sur des corps différents"
    R = [Zp(0,p)] * max(len(F),len(G))
    m = min(len(F), len(G))
    for i in range(m):
        R[i] = F[i] + G[i]
    for i in range(m,len(F)):
        R[i] = F[i]
    for i in range(m, len(G)):
        R[i] = G[i]
    while len(R) > 0 and R[-1].est_nul(): 
        R.pop(-1)
    return R

def MultiplicationNaive(F, G):
    if len(F) == 0 or len(G) == 0: return []
    p = F[0].modulus()
    assert p == G[0].modulus(), "les polynômes sont définis sur des corps différents"

    n = len(F) + len(G) - 1
    R = [Zp(0, p)] * n
    for i in range(len(F)):
        for j in range(len(G)):
            R[i+j] += F[i] * G[j]
    return R

def ProchainePuissance(n):
    return 1<<(n-1).bit_length()