M = 998244353; R = [1, 1] def ntt(P): n = len(P); L = len(bin(n))-3; Z = [0]*n; k = 1 while len(R) < n: u = pow(3, M//(2*len(R)), M) # 3 is a primitive root of M for i in range(len(R), 2*len(R)): R.append(R[i//2]*(u if i&1 else 1)%M) for i in range(n): Z[i] = (Z[i//2]|(i&1)<