import sys readline=sys.stdin.readline def 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]%mod poly[i+j]%=mod return poly """ prim_root=3 prim_root_inve=332748118 def DFT(polynomial,n,inverse=False): if inverse: for bit in range(1,n+1): a=1<>bit,mod) U=[1] for _ in range(a): U.append(U[-1]*x%mod) for i in range(1<>bit,mod) U=[1] for _ in range(a): U.append(U[-1]*x%mod) for i in range(1<self.max_degree+1: self.polynomial=polynomial[:self.max_degree+1] else: self.polynomial=polynomial self.mod=mod self.eps=eps def __eq__(self,other): if type(other)!=Polynomial: return False if len(self.polynomial)!=len(other.polynomial): return False for i in range(len(self.polynomial)): if self.epsself.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 prod def __truediv__(self,other): if type(other)==Polynomial: assert other.polynomial for n in range(len(other.polynomial)): if self.epsn for i in range(n): assert abs(self.polynomial[i])<=self.eps self_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.mod for i in range(max(0,len(self_polynomial)-len(other_polynomial)+1),len(self_polynomial)): if self.eps>bit,self.mod) U=[1] for _ in range(a): U.append(U[-1]*x%self.mod) for i in range(1<>bit,self.mod) U=[1] for _ in range(a): U.append(U[-1]*x%self.mod) for i in range(1<