def Berlekamp_Massey(A,mod): n = len(A) B, C = [1], [1] l, m, p = 0, 1, 1 for i in range(n): d = A[i] for j in range(1, l + 1): d += C[j] * A[i - j] d %= mod if d == 0: m += 1 continue T = C.copy() q = pow(p, mod - 2, mod) * d % mod if len(C) < len(B) + m: C += [0] * (len(B) + m - len(C)) for j, b in enumerate(B): C[j + m] -= q * b C[j + m] %= mod if 2 * l <= i: B = T l, m, p = i + 1 - l, 1, d else: m += 1 res = [-c % mod for c in C[1:]] return res def BMBM(A,N,mod): deno=[1]+[-c for c in Berlekamp_Massey(A,mod)] nume=[0]*(len(deno)-1) for i in range(len(A)): for j in range(len(deno)): if i+j