import sys input = sys.stdin.readline from copy import deepcopy # FFT # mod=998244353 における、NTTによる高速フーリエ変換、畳み込み # 他の提出を参考にしており、あまり理解できていません…… mod=998244353 Weight=[1, 998244352, 911660635, 372528824, 929031873, 452798380, 922799308, 781712469, 476477967, 166035806, 258648936, 584193783, 63912897, 350007156, 666702199, 968855178, 629671588, 24514907, 996173970, 363395222, 565042129, 733596141, 267099868, 15311432, 0] Weight_inv=[1, 998244352, 86583718, 509520358, 337190230, 87557064, 609441965, 135236158, 304459705, 685443576, 381598368, 335559352, 129292727, 358024708, 814576206, 708402881, 283043518, 3707709, 121392023, 704923114, 950391366, 428961804, 382752275, 469870224, 0] def fft(A,n,h,inverse=0): if inverse==0: for i in range(h): m=1<<(h-i-1) for j in range(1<=2: Y=[] for i in range(0,len(X),2): if i+1