import math MOD = 998244353 # https://github.com/shakayami/ACL-for-python # https://github.com/shakayami/ACL-for-python/blob/master/convolution.py class FFT(): def primitive_root_constexpr(self,m): if m==2:return 1 if m==167772161:return 3 if m==469762049:return 3 if m==754974721:return 11 if m==998244353:return 3 divs=[0]*20 divs[0]=2 cnt=1 x=(m-1)//2 while(x%2==0):x//=2 i=3 while(i*i<=x): if (x%i==0): divs[cnt]=i cnt+=1 while(x%i==0): x//=i i+=2 if x>1: divs[cnt]=x cnt+=1 g=2 while(1): ok=True for i in range(cnt): if pow(g,(m-1)//divs[i],m)==1: ok=False break if ok: return g g+=1 def bsf(self,x): res=0 while(x%2==0): res+=1 x//=2 return res rank2=0 root=[] iroot=[] rate2=[] irate2=[] rate3=[] irate3=[] def __init__(self,MOD): self.mod=MOD self.g=self.primitive_root_constexpr(self.mod) self.rank2=self.bsf(self.mod-1) self.root=[0 for i in range(self.rank2+1)] self.iroot=[0 for i in range(self.rank2+1)] self.rate2=[0 for i in range(self.rank2)] self.irate2=[0 for i in range(self.rank2)] self.rate3=[0 for i in range(self.rank2-1)] self.irate3=[0 for i in range(self.rank2-1)] self.root[self.rank2]=pow(self.g,(self.mod-1)>>self.rank2,self.mod) self.iroot[self.rank2]=pow(self.root[self.rank2],self.mod-2,self.mod) for i in range(self.rank2-1,-1,-1): self.root[i]=(self.root[i+1]**2)%self.mod self.iroot[i]=(self.iroot[i+1]**2)%self.mod prod=1;iprod=1 for i in range(self.rank2-1): self.rate2[i]=(self.root[i+2]*prod)%self.mod self.irate2[i]=(self.iroot[i+2]*iprod)%self.mod prod=(prod*self.iroot[i+2])%self.mod iprod=(iprod*self.root[i+2])%self.mod prod=1;iprod=1 for i in range(self.rank2-2): self.rate3[i]=(self.root[i+3]*prod)%self.mod self.irate3[i]=(self.iroot[i+3]*iprod)%self.mod prod=(prod*self.iroot[i+3])%self.mod iprod=(iprod*self.root[i+3])%self.mod def butterfly(self,a): n=len(a) h=(n-1).bit_length() LEN=0 while(LEN> 1] += (1 if i % 2 == 0 else -1) # 分子 g = [0] * (N + 1) for i in range(0, N // (K + 1) + 1): g[i * (K + 1)] = f[i] # 逆数にする f = fps_inverse(fft, f) # かける ans = fft.convolution(g, f, N + 1) print(" ".join(str(ans[i] % MOD) for i in range(1, N + 1)))