class FPS: sum_e=(911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497) sum_ie=(86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951) mod=998244353 g=3 def butterfly(self,a): n=len(a) h=(n-1).bit_length() for ph in range(1,h+1): w=1<<(ph-1) p=1<<(h-ph) now=1 for s in range(w): offset=s<<(h-ph+1) for i in range(p): l=a[i+offset] r=a[i+offset+p]*now r%=self.mod a[i+offset]=l+r a[i+offset]%=self.mod a[i+offset+p]=l-r a[i+offset+p]%=self.mod now*=self.sum_e[(~s & -~s).bit_length()-1] now%=self.mod def butterfly_inv(self,a): n=len(a) h=(n-1).bit_length() for ph in range(h,0,-1): w=1<<(ph-1) p=1<<(h-ph) inow=1 for s in range(w): offset=s<<(h-ph+1) for i in range(p): l=a[i+offset] r=a[i+offset+p] a[i+offset]=l+r a[i+offset]%=self.mod a[i+offset+p]=(l-r)*inow a[i+offset+p]%=self.mod inow*=self.sum_ie[(~s & -~s).bit_length()-1] inow%=self.mod def convolution(self,a,b): n=len(a);m=len(b) if not(a) or not(b): return [] if min(n,m)<=40: if nx: z=[Y[i][j<<1][(len(Y[i][j<<1])>>1)+k] for k in range(-(x>>1),(x>>1)+1)] Y[i][j<<1]=z if len(Y[i][(j<<1)+1])>x: z=[Y[i][(j<<1)+1][(len(Y[i][(j<<1)+1])>>1)+k] for k in range(-(x>>1),(x>>1)+1)] Y[i][(j<<1)+1]=z ANS=0 P=2*M+1 V=pow(P,N,mod) W=pow(P,mod-2,mod) U=1 for i in range(1,N+1): V=V*W%mod U=U*P%mod ANS+=(U-Y[0][i][0])*V*(N-i+1) print(ANS*pow(2,mod-2,mod)%mod)