class Convoluter: def __init__(self): self.primitive=self.__primitive_root() self.__build_up() def __primitive_root(self): p=Mod if p==2: return 1 if p==998244353: return 3 if p==10**9+7: return 5 if p==163577857: return 23 if p==167772161: return 3 if p==469762049: return 3 fac=[] q=2 v=p-1 while v>=q*q: e=0 while v%q==0: e+=1 v//=q if e>0: fac.append(q) q+=1 if v>1: fac.append(v) g=2 while g>rank2, Mod) iroot[-1]=pow(root[-1], Mod-2, Mod) for i in range(rank2)[::-1]: root[i]=root[i+1]*root[i+1]%Mod iroot[i]=iroot[i+1]*iroot[i+1]%Mod prod=iprod=1 for i in range(rank2-1): rate2[i]=root[i+2]*prod%Mod irate2[i]=iroot[i+2]*prod%Mod prod*=iroot[i+2]; prod%=Mod iprod*=root[i+2]; iprod%=Mod prod=iprod = 1 for i in range(rank2-2): rate3[i]=root[i + 3]*prod%Mod irate3[i]=iroot[i + 3]*iprod%Mod prod*=iroot[i + 3]; prod%=Mod iprod*=root[i + 3]; iprod%=Mod self.root=root; self.iroot=iroot self.rate2=rate2; self.irate2=irate2 self.rate3=rate3; self.irate3=irate3 #参考元 https://judge.yosupo.jp/submission/72676 def NTT(self,A): """A に Mod を法とする数論変換を施す ※ Mod はグローバル変数から指定 References: https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp https://judge.yosupo.jp/submission/72676 """ N=len(A) H=(N-1).bit_length() l=0 I=self.root[2] rate2=self.rate2; rate3=self.rate3 while l=2: a,A=heappop(Q) b,B=heappop(Q) heappush(Q,(a+b,Conv.Convolution(A,B))) _,A=heappop(Q) X=0 for d,a in enumerate(A): if d>=1: X+=Fact[d]*a X%=Mod print(X)