結果
問題 | No.1302 Random Tree Score |
ユーザー |
![]() |
提出日時 | 2023-04-24 03:13:34 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 446 ms / 3,000 ms |
コード長 | 32,605 bytes |
コンパイル時間 | 444 ms |
コンパイル使用メモリ | 16,512 KB |
実行使用メモリ | 21,504 KB |
最終ジャッジ日時 | 2024-11-08 07:37:19 |
合計ジャッジ時間 | 5,393 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
import mathimport sysreadline=sys.stdin.readlinemod=998244353def NTT(polynomial0,polynomial1):"""if len(polynomial0)*len(polynomial1)<=50:poly=[0]*(len(polynomial0)+len(polynomial1)-1)for i in range(len(polynomial0)):for j in range(len(polynomial1)):poly[i+j]+=polynomial0[i]*polynomial1[j]%modpoly[i+j]%=modreturn poly"""if mod==998244353:prim_root=3prim_root_inve=332748118else:prim_root=Primitive_Root(mod)prim_root_inve=MOD(mod).Pow(prim_root,-1)def DFT(polynomial,n,inverse=False):if inverse:for bit in range(1,n+1):a=1<<bit-1x=pow(prim_root,mod-1>>bit,mod)U=[1]for _ in range(a):U.append(U[-1]*x%mod)for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=(polynomial[s]+polynomial[t]*U[j])%mod,(polynomial[s]-polynomial[t]*U[j])%modx=pow((mod+1)//2,n,mod)for i in range(1<<n):polynomial[i]*=xpolynomial[i]%=modelse:for bit in range(n,0,-1):a=1<<bit-1x=pow(prim_root_inve,mod-1>>bit,mod)U=[1]for _ in range(a):U.append(U[-1]*x%mod)for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=(polynomial[s]+polynomial[t])%mod,U[j]*(polynomial[s]-polynomial[t])%modl=len(polynomial0)+len(polynomial1)-1n=(len(polynomial0)+len(polynomial1)-2).bit_length()polynomial0=polynomial0+[0]*((1<<n)-len(polynomial0))polynomial1=polynomial1+[0]*((1<<n)-len(polynomial1))DFT(polynomial0,n)DFT(polynomial1,n)ntt=[x*y%mod for x,y in zip(polynomial0,polynomial1)]DFT(ntt,n,inverse=True)ntt=ntt[:l]return nttdef NTT_Pow(polynomial,N):if N==0:return [1]if N==1:return [x for x in polynomial]if mod==998244353:prim_root=3prim_root_inve=332748118else:prim_root=Primitive_Root(mod)prim_root_inve=MOD(mod).Pow(prim_root,-1)def DFT(polynomial,n,inverse=False):if inverse:for bit in range(1,n+1):a=1<<bit-1x=pow(prim_root,mod-1>>bit,mod)U=[1]for _ in range(a):U.append(U[-1]*x%mod)for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=(polynomial[s]+polynomial[t]*U[j])%mod,(polynomial[s]-polynomial[t]*U[j])%modx=pow((mod+1)//2,n,mod)for i in range(1<<n):polynomial[i]*=xpolynomial[i]%=modelse:for bit in range(n,0,-1):a=1<<bit-1x=pow(prim_root_inve,mod-1>>bit,mod)U=[1]for _ in range(a):U.append(U[-1]*x%mod)for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=(polynomial[s]+polynomial[t])%mod,U[j]*(polynomial[s]-polynomial[t])%modn=((len(polynomial)-1)*N).bit_length()ntt=polynomial+[0]*((1<<n)-len(polynomial))DFT(ntt,n)for i in range(1<<n):ntt[i]=pow(ntt[i],N,mod)DFT(ntt,n,inverse=True)ntt=ntt[:(len(polynomial)-1)*N+1]return nttdef Extended_Euclid(n,m):stack=[]while m:stack.append((n,m))n,m=m,n%mif n>=0:x,y=1,0else:x,y=-1,0for i in range(len(stack)-1,-1,-1):n,m=stack[i]x,y=y,x-(n//m)*yreturn x,yclass MOD:def __init__(self,p,e=None):self.p=pself.e=eif self.e==None:self.mod=self.pelse:self.mod=self.p**self.edef Pow(self,a,n):a%=self.modif n>=0:return pow(a,n,self.mod)else:assert math.gcd(a,self.mod)==1x=Extended_Euclid(a,self.mod)[0]return pow(x,-n,self.mod)def Build_Fact(self,N):assert N>=0self.factorial=[1]if self.e==None:for i in range(1,N+1):self.factorial.append(self.factorial[-1]*i%self.mod)else:self.cnt=[0]*(N+1)for i in range(1,N+1):self.cnt[i]=self.cnt[i-1]ii=iwhile ii%self.p==0:ii//=self.pself.cnt[i]+=1self.factorial.append(self.factorial[-1]*ii%self.mod)self.factorial_inve=[None]*(N+1)self.factorial_inve[-1]=self.Pow(self.factorial[-1],-1)for i in range(N-1,-1,-1):ii=i+1while ii%self.p==0:ii//=self.pself.factorial_inve[i]=(self.factorial_inve[i+1]*ii)%self.moddef Fact(self,N):if N<0:return 0retu=self.factorial[N]if self.e!=None and self.cnt[N]:retu*=pow(self.p,self.cnt[N],self.mod)%self.modretu%=self.modreturn retudef Fact_Inve(self,N):if self.e!=None and self.cnt[N]:return Nonereturn self.factorial_inve[N]def Comb(self,N,K,divisible_count=False):if K<0 or K>N:return 0retu=self.factorial[N]*self.factorial_inve[K]%self.mod*self.factorial_inve[N-K]%self.modif self.e!=None:cnt=self.cnt[N]-self.cnt[N-K]-self.cnt[K]if divisible_count:return retu,cntelse:retu*=pow(self.p,cnt,self.mod)retu%=self.modreturn retudef Tonelli_Shanks(N,p):if pow(N,p>>1,p)==p-1:retu=Noneelif p%4==3:retu=pow(N,(p+1)//4,p)else:for nonresidue in range(1,p):if pow(nonresidue,p>>1,p)==p-1:breakpp=p-1cnt=0while pp%2==0:pp//=2cnt+=1s=pow(N,pp,p)retu=pow(N,(pp+1)//2,p)for i in range(cnt-2,-1,-1):if pow(s,1<<i,p)==p-1:s*=pow(nonresidue,p>>1+i,p)s%=pretu*=pow(nonresidue,p>>2+i,p)retu%=preturn retudef FFT(polynomial0,polynomial1,digit=10**5):def DFT(polynomial,n,inverse=False):if inverse:primitive_root=[math.cos(-i*2*math.pi/(1<<n))+math.sin(-i*2*math.pi/(1<<n))*1j for i in range(1<<n)]else:primitive_root=[math.cos(i*2*math.pi/(1<<n))+math.sin(i*2*math.pi/(1<<n))*1j for i in range(1<<n)]if inverse:for bit in range(1,n+1):a=1<<bit-1for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=polynomial[s]+polynomial[t]*primitive_root[j<<n-bit],polynomial[s]-polynomial[t]*primitive_root[j<<n-bit]else:for bit in range(n,0,-1):a=1<<bit-1for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=polynomial[s]+polynomial[t],primitive_root[j<<n-bit]*(polynomial[s]-polynomial[t])def FFT_(polynomial0,polynomial1):N0=len(polynomial0)N1=len(polynomial1)N=N0+N1-1n=(N-1).bit_length()polynomial0=polynomial0+[0]*((1<<n)-N0)polynomial1=polynomial1+[0]*((1<<n)-N1)DFT(polynomial0,n)DFT(polynomial1,n)fft=[x*y for x,y in zip(polynomial0,polynomial1)]DFT(fft,n,inverse=True)fft=[round((fft[i]/(1<<n)).real) for i in range(N)]return fftN0=len(polynomial0)N1=len(polynomial1)N=N0+N1-1polynomial00,polynomial01=[None]*N0,[None]*N0polynomial10,polynomial11=[None]*N1,[None]*N1for i in range(N0):polynomial00[i],polynomial01[i]=divmod(polynomial0[i],digit)for i in range(N1):polynomial10[i],polynomial11[i]=divmod(polynomial1[i],digit)polynomial=[0]*(N)a=digit**2-digitfor i,x in enumerate(FFT_(polynomial00,polynomial10)):polynomial[i]+=x*aa=digit-1for i,x in enumerate(FFT_(polynomial01,polynomial11)):polynomial[i]-=x*afor i,x in enumerate(FFT_([x1+x2 for x1,x2 in zip(polynomial00,polynomial01)],[x1+x2 for x1,x2 in zip(polynomial10,polynomial11)])):polynomial[i]+=x*digitreturn polynomialdef FFT_Pow(polynomial,N):if N==0:return [1]if N==1:return [x for x in polynomial]def DFT(polynomial,n,inverse=False):if inverse:primitive_root=[math.cos(-i*2*math.pi/(1<<n))+math.sin(-i*2*math.pi/(1<<n))*1j for i in range(1<<n)]else:primitive_root=[math.cos(i*2*math.pi/(1<<n))+math.sin(i*2*math.pi/(1<<n))*1j for i in range(1<<n)]if inverse:for bit in range(1,n+1):a=1<<bit-1for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=polynomial[s]+polynomial[t]*primitive_root[j<<n-bit],polynomial[s]-polynomial[t]*primitive_root[j<<n-bit]else:for bit in range(n,0,-1):a=1<<bit-1for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=polynomial[s]+polynomial[t],primitive_root[j<<n-bit]*(polynomial[s]-polynomial[t])n=((len(polynomial)-1)*N).bit_length()fft=polynomial+[0]*((1<<n)-len(polynomial))DFT(fft,n)for i in range(1<<n):fft[i]=pow(fft[i],N)DFT(fft,n,inverse=True)fft=[round((fft[i]/(1<<n)).real) for i in range((len(polynomial)-1)*N+1)]return fftclass Polynomial:def __init__(self,polynomial,max_degree=-1,eps=0,mod=0):self.max_degree=max_degreeif self.max_degree!=-1 and len(polynomial)>self.max_degree+1:self.polynomial=polynomial[:self.max_degree+1]else:self.polynomial=polynomialself.mod=modself.eps=epsdef __eq__(self,other):if type(other)!=Polynomial:return Falseif len(self.polynomial)!=len(other.polynomial):return Falsefor i in range(len(self.polynomial)):if self.eps<abs(self.polynomial[i]-other.polynomial[i]):return Falsereturn Truedef __ne__(self,other):if type(other)!=Polynomial:return Trueif len(self.polynomial)!=len(other.polynomial):return Truefor i in range(len(self.polynomial)):if self.eps<abs(self.polynomial[i]-other.polynomial[i]):return Truereturn Falsedef __add__(self,other):if type(other)==Polynomial:summ=[0]*max(len(self.polynomial),len(other.polynomial))for i in range(len(self.polynomial)):summ[i]+=self.polynomial[i]for i in range(len(other.polynomial)):summ[i]+=other.polynomial[i]if self.mod:for i in range(len(summ)):summ[i]%=self.modelse:summ=[x for x in self.polynomial] if self.polynomial else [0]summ[0]+=otherif self.mod:summ[0]%=self.modwhile summ and abs(summ[-1])<=self.eps:summ.pop()summ=Polynomial(summ,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return summdef __sub__(self,other):if type(other)==Polynomial:diff=[0]*max(len(self.polynomial),len(other.polynomial))for i in range(len(self.polynomial)):diff[i]+=self.polynomial[i]for i in range(len(other.polynomial)):diff[i]-=other.polynomial[i]if self.mod:for i in range(len(diff)):diff[i]%=self.modelse:diff=[x for x in self.polynomial] if self.polynomial else [0]diff[0]-=otherif self.mod:diff[0]%=self.modwhile diff and abs(diff[-1])<=self.eps:diff.pop()diff=Polynomial(diff,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return diffdef __mul__(self,other):if type(other)==Polynomial:if self.max_degree==-1:prod=[0]*(len(self.polynomial)+len(other.polynomial)-1)for i in range(len(self.polynomial)):for j in range(len(other.polynomial)):prod[i+j]+=self.polynomial[i]*other.polynomial[j]else:prod=[0]*min(len(self.polynomial)+len(other.polynomial)-1,self.max_degree+1)for i in range(len(self.polynomial)):for j in range(min(len(other.polynomial),self.max_degree+1-i)):prod[i+j]+=self.polynomial[i]*other.polynomial[j]if self.mod:for i in range(len(prod)):prod[i]%=self.modelse:if self.mod:prod=[x*other%self.mod for x in self.polynomial]else:prod=[x*other for x in self.polynomial]while prod and abs(prod[-1])<=self.eps:prod.pop()prod=Polynomial(prod,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return proddef __matmul__(self,other):assert type(other)==Polynomialif self.mod:prod=NTT(self.polynomial,other.polynomial)else:prod=FFT(self.polynomial,other.polynomial)if self.max_degree!=-1 and len(prod)>self.max_degree+1:prod=prod[:self.max_degree+1]while prod and abs(prod[-1])<=self.eps:prod.pop()prod=Polynomial(prod,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return proddef __pow__(self,other):if other==0:prod=Polynomial([1],max_degree=self.max_degree,eps=self.eps,mod=self.mod)elif other==1:prod=Polynomial([x for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)else:prod=[1]doub=self.polynomialif self.mod:convolve=NTTconvolve_Pow=NTT_Powelse:convolve=FFTconvolve_Pow=FFT_Powwhile other>=2:if other&1:prod=convolve(prod,doub)if self.max_degree!=-1:prod=prod[:self.max_degree+1]doub=convolve_Pow(doub,2)if self.max_degree!=-1:doub=doub[:self.max_degree+1]other>>=1prod=convolve(prod,doub)if self.max_degree!=-1:prod=prod[:self.max_degree+1]prod=Polynomial(prod,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return proddef __truediv__(self,other):if type(other)==Polynomial:assert other.polynomialfor n in range(len(other.polynomial)):if self.eps<abs(other.polynomial[n]):breakassert len(self.polynomial)>nfor i in range(n):assert abs(self.polynomial[i])<=self.epsself_polynomial=self.polynomial[n:]other_polynomial=other.polynomial[n:]if self.mod:inve=MOD(self.mod).Pow(other_polynomial[0],-1)else:inve=1/other_polynomial[0]quot=[]for i in range(len(self_polynomial)-len(other_polynomial)+1):if self.mod:quot.append(self_polynomial[i]*inve%self.mod)else:quot.append(self_polynomial[i]*inve)for j in range(len(other_polynomial)):self_polynomial[i+j]-=other_polynomial[j]*quot[-1]if self.mod:self_polynomial[i+j]%=self.modfor i in range(max(0,len(self_polynomial)-len(other_polynomial)+1),len(self_polynomial)):if self.eps<abs(self_polynomial[i]):assert self.max_degree!=-1self_polynomial=self_polynomial[-len(other_polynomial)+1:]+[0]*(len(other_polynomial)-1-len(self_polynomial))while len(quot)<=self.max_degree:self_polynomial.append(0)if self.mod:quot.append(self_polynomial[0]*inve%self.mod)self_polynomial=[(self_polynomial[i]-other_polynomial[i]*quot[-1])%self.mod for i in range(1,len(self_polynomial))]else:quot.append(self_polynomial[0]*inve)self_polynomial=[(self_polynomial[i]-other_polynomial[i]*quot[-1]) for i in range(1,len(self_polynomial))]breakquot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=self.mod)else:assert self.eps<abs(other)if self.mod:inve=MOD(self.mod).Pow(other,-1)quot=Polynomial([x*inve%self.mod for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)else:quot=Polynomial([x/other for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)return quotdef __rtruediv__(self,other):assert self.polynomial and self.eps<self.polynomial[0]assert self.max_degree!=-1if self.mod:quot=[MOD(self.mod).Pow(self.polynomial[0],-1)]if self.mod==998244353:prim_root=3prim_root_inve=332748118else:prim_root=Primitive_Root(self.mod)prim_root_inve=MOD(self.mod).Pow(prim_root,-1)def DFT(polynomial,n,inverse=False):polynomial=polynomial+[0]*((1<<n)-len(polynomial))if inverse:for bit in range(1,n+1):a=1<<bit-1x=pow(prim_root,self.mod-1>>bit,self.mod)U=[1]for _ in range(a):U.append(U[-1]*x%self.mod)for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=(polynomial[s]+polynomial[t]*U[j])%self.mod,(polynomial[s]-polynomial[t]*U[j])%self.modx=pow((self.mod+1)//2,n,self.mod)for i in range(1<<n):polynomial[i]*=xpolynomial[i]%=self.modelse:for bit in range(n,0,-1):a=1<<bit-1x=pow(prim_root_inve,self.mod-1>>bit,self.mod)U=[1]for _ in range(a):U.append(U[-1]*x%self.mod)for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=(polynomial[s]+polynomial[t])%self.mod,U[j]*(polynomial[s]-polynomial[t])%self.modreturn polynomialelse:quot=[1/self.polynomial[0]]def DFT(polynomial,n,inverse=False):N=len(polynomial)if inverse:primitive_root=[math.cos(-i*2*math.pi/(1<<n))+math.sin(-i*2*math.pi/(1<<n))*1j for i in range(1<<n)]else:primitive_root=[math.cos(i*2*math.pi/(1<<n))+math.sin(i*2*math.pi/(1<<n))*1j for i in range(1<<n)]polynomial=polynomial+[0]*((1<<n)-N)if inverse:for bit in range(1,n+1):a=1<<bit-1for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=polynomial[s]+polynomial[t]*primitive_root[j<<n-bit],polynomial[s]-polynomial[t]*primitive_root[j<<n-bit]for i in range(1<<n):polynomial[i]=round((polynomial[i]/(1<<n)).real)else:for bit in range(n,0,-1):a=1<<bit-1for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=polynomial[s]+polynomial[t],primitive_root[j<<n-bit]*(polynomial[s]-polynomial[t])return polynomialfor n in range(self.max_degree.bit_length()):prev=quotif self.mod:quot=DFT([x*y%self.mod*y%self.mod for x,y in zip(DFT(self.polynomial[:1<<n+1],n+2),DFT(prev,n+2))],n+2,inverse=True)[:1<<n+1]else:quot=DFT([x*y*y for x,y in zip(DFT(self.polynomial[:1<<n+1],n+2),DFT(prev,n+2))],n+2,inverse=True)[:1<<n+1]for i in range(1<<n):quot[i]=2*prev[i]-quot[i]if self.mod:quot[i]%=self.modfor i in range(1<<n,1<<n+1):quot[i]=-quot[i]if self.mod:quot[i]%=self.modquot=quot[:self.max_degree+1]if abs(other-1)>self.eps:for i in range(len(quot)):quot[i]*=otherif self.mod:quot[i]%=self.modquot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return quotdef __floordiv__(self,other):assert type(other)==Polynomialquot=[0]*(len(self.polynomial)-len(other.polynomial)+1)rema=[x for x in self.polynomial]if self.mod:inve=MOD(self.mod).Pow(other.polynomial[-1],-1)for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*inve%self.modfor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]rema[i+j]%=self.modelse:inve=1/other.polynomial[-1]for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*invefor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]quot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return quotdef __mod__(self,other):assert type(other)==Polynomialquot=[0]*(len(self.polynomial)-len(other.polynomial)+1)rema=[x for x in self.polynomial]if self.mod:inve=MOD(self.mod).Pow(other.polynomial[-1],-1)for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*inve%self.modfor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]rema[i+j]%=self.modelse:inve=1/other.polynomial[-1]for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*invefor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]while rema and abs(rema[-1])<=self.eps:rema.pop()rema=Polynomial(rema,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return remadef __divmod__(self,other):assert type(other)==Polynomialquot=[0]*(len(self.polynomial)-len(other.polynomial)+1)rema=[x for x in self.polynomial]if self.mod:inve=MOD(self.mod).Pow(other.polynomial[-1],-1)for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*inve%self.modfor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]rema[i+j]%=self.modelse:inve=1/other.polynomial[-1]for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*invefor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]while rema and abs(rema[-1])<=self.eps:rema.pop()quot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=self.mod)rema=Polynomial(rema,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return quot,remadef __neg__(self):if self.mod:nega=Polynomial([(-x)%self.mod for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)else:nega=Polynomial([-x for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)return negadef __pos__(self):posi=Polynomial([x for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)return posidef __bool__(self):return self.polynomialdef __getitem__(self,n):if type(n)==int:if n<=len(self.polynomial)-1:return self.polynomial[n]else:return 0else:return Polynomial(polynomial=self.polynomial[n],max_degree=self.max_degree,eps=self.eps,mod=self.mod)def __setitem__(self,n,a):if self.mod:a%=self.modif self.max_degree==-1 or n<=self.max_degree:if n<=len(self.polynomial)-1:self.polynomial[n]=aelif self.eps<abs(a):self.polynomial+=[0]*(n-len(self.polynomial))+[a]def __iter__(self):for x in self.polynomial:yield xdef __call__(self,x):retu=0pow_x=1for i in range(len(self.polynomial)):retu+=pow_x*self.polynomial[i]pow_x*=xif self.mod:retu%=self.modpow_x%=self.modreturn retudef __str__(self):return "["+", ".join(map(str,self.polynomial))+"]"def __len__(self):return len(self.polynomial)def differential(self):if self.mod:differential=[x*i%self.mod for i,x in enumerate(self.polynomial[1:],1)]else:differential=[x*i for i,x in enumerate(self.polynomial[1:],1)]return Polynomial(differential,max_degree=self.max_degree,eps=self.eps,mod=self.mod)def integral(self):if self.mod:integral=[0]+[x*MOD(mod).Pow(i+1,-1)%self.mod for i,x in enumerate(self.polynomial)]else:integral=[0]+[x/(i+1) for i,x in enumerate(self.polynomial)]while integral and abs(integral[-1])<=self.eps:integral.pop()return Polynomial(integral,max_degree=self.max_degree,eps=self.eps,mod=self.mod)def log(self):assert self.max_degree!=-1assert self.polynomial and abs(self.polynomial[0]-1)<=self.epslog=(1/self)if self.mod:log=Polynomial(NTT(self.differential().polynomial,log.polynomial),max_degree=self.max_degree,eps=self.eps,mod=self.mod)else:log=Polynomial(FFT(self.differential().polynomial,log.polynomial),max_degree=self.max_degree,eps=self.eps,mod=self.mod)log=log.integral()return logdef Newton(self,n0,f,differentiated_f=None):newton=[n0]while len(newton)<self.max_degree+1:prev=newtonif differentiated_f==None:newton=f(prev,self.polynomial)else:newton=f(prev)for i in range(min(len(self.polynomial),len(newton))):newton[i]-=self.polynomial[i]newton[i]%=self.modif self.mod:newton=NTT(newton,(1/Polynomial(differentiated_f(prev),max_degree=len(newton)-1,eps=self.eps,mod=self.mod)).polynomial)[:len(newton)]else:newton=FFT(newton,(1/Polynomial(differentiated_f(prev),max_degree=len(newton)-1,eps=self.eps,mod=self.mod)).polynomial)[:len(newton)]for i in range(len(newton)):newton[i]=-newton[i]newton[i]%=self.modfor i in range(len(prev)):newton[i]+=prev[i]newton[i]%=self.modnewton=newton[:self.max_degree+1]while newton and newton[-1]<=self.eps:newton.pop()return Polynomial(newton,max_degree=self.max_degree,eps=self.eps,mod=self.mod)def sqrt(self):if self.polynomial:for cnt0 in range(len(self.polynomial)):if self.polynomial[cnt0]:breakif cnt0%2:sqrt=Noneelse:if self.mod:n0=Tonelli_Shanks(self.polynomial[cnt0],self.mod)else:if self.polynomial[cnt0]>=self.eps:n0=self.polynomial[cnt0]**.5if n0==None:sqrt=Noneelse:def f(prev):if self.mod:return NTT_Pow(prev,2)+[0]else:return FFT_Pow(prev,2)+[0]def differentiated_f(prev):retu=[0]*(2*len(prev)-1)for i in range(len(prev)):retu[i]+=2*prev[i]if self.mod:retu[i]%self.modreturn retusqrt=[0]*(cnt0//2)+Polynomial(self.polynomial[cnt0:],max_degree=self.max_degree-cnt0//2,mod=self.mod).Newton(n0,f,differentiated_f).polynomialsqrt=Polynomial(sqrt,max_degree=self.max_degree,eps=self.eps,mod=self.mod)else:sqrt=Polynomial([],max_degree=self.max_degree,eps=self.eps,mod=self.mod)return sqrtdef exp(self):assert not self.polynomial or abs(self.polynomial[0])<=self.epsdef f(prev,poly):newton=Polynomial(prev,max_degree=2*len(prev)-1,eps=self.eps,mod=self.mod).log().polynomialnewton+=[0]*(2*len(prev)-len(newton))for i in range(min(len(poly),len(newton))):newton[i]-=poly[i]if self.mod:for i in range(len(newton)):newton[i]%=self.modif self.mod:return NTT(prev,newton)[:2*len(prev)]else:return FFT(prev,newton)[:2*len(prev)]return Polynomial(self.polynomial,max_degree=self.max_degree,mod=self.mod).Newton(1,f)def Degree(self):return len(self.polynomial)-1N=int(readline())mod=998244353MD=MOD(mod)MD.Build_Fact(N)#(x+1)^N*e^Nxans=0for i in range(N-1):ans+=MD.Comb(N,N-2-i)*MD.Fact_Inve(i)%mod*pow(N,i,mod)%modans*=MD.Fact(N-2)*pow(N,(mod-2)*(N-2),mod)%modans%=modprint(ans)