import numpy as np from numpy.fft import rfft,irfft mod = 998244353 def convolve(f, g): fft_len = 1 while 2 * fft_len < len(f) + len(g) - 1: fft_len *= 2 fft_len *= 2 Ff = np.fft.rfft(f, fft_len) Fg = np.fft.rfft(g, fft_len) Fh = Ff * Fg h = np.fft.irfft(Fh, fft_len) h = np.rint(h).astype(np.int64) return h[:len(f) + len(g) - 1] def convolve2(f, g): f1, f2 = np.divmod(f, 1 << 15) g1, g2 = np.divmod(g, 1 << 15) a = convolve(f1, g1)%mod c = convolve(f2, g2)%mod b = (convolve(f1+f2, g1+g2)-(a+c))%mod h = (a << 30) + (b << 15) + c return h%mod class poly(object): def __init__(self, coef): if isinstance(coef, int): coef = [coef] self.coef = np.array([c%mod for c in coef], dtype=np.int64) self.n = len(coef) def __getitem__(self, item): return poly(self.coef[item]) def __setitem__(self, key, value): self.coef[key] = value%mod def __len__(self): return self.n def __add__(p, q): n = max(len(p),len(q)) return poly((p.pad(n).coef+q.pad(n).coef)%mod) def __sub__(p, q): n = max(len(p),len(q)) p.pad(n) q.pad(n) return poly((p.pad(n).coef-q.pad(n).coef)%mod) def __mul__(p, q): return poly(convolve2(p.coef,q.coef)) def __truediv__(p, q): return p*q.inv() def pad(self, n): if len(self)1: p1 = q.popleft() p2 = q.popleft() p = p1*p2 q.append(p) poly_ans = poly(-1)*q[0].log(M+1) ans = [] for i in range(M): ans.append((i+1)*poly_ans.coef[i+1]%mod) print(*ans)