class Modulo_Polynominal(): def __init__(self,Poly,Max_Degree=2*10**5,Char="X"): from itertools import zip_longest """多項式の定義 P:係数のリスト C:文字 Max_Degree ※Mod:法はグローバル変数から指定 """ self.Poly=[p%Mod for p in Poly[:Max_Degree]] self.Char=Char self.Max_Degree=Max_Degree self.minus=10**7 def __str__(self): if bool(self): M=[(k,a) for k,a in enumerate(self.Poly) if a] for i in range(len(M)): k,a=M[i] if Mod-a<=self.minus: M[i]=(k,a-Mod) A=["{} {} ^ {} ".format(a,self.Char,k) for k,a in M] S=" "+" + ".join(A) S=S.replace(" + -"," - ") S=S.replace(" {} ^ 0 ".format(self.Char),"") S=S.replace(" {} ^ 1 ".format(self.Char)," "+self.Char+" ") S=S.replace(" 1 {} ".format(self.Char),self.Char+" ") S=S.replace(" -1 {} ".format(self.Char),"-"+self.Char+" ") S=S.replace(" ","") else: S="0" S+=" (mod (Z/ {0} Z)[{1}]/ ({1}^{2}))".format(Mod,self.Char,self.Max_Degree) return S.strip() def __repr__(self): return self.__str__() #= def __eq__(self,other): if self.Max_Degree!=other.Max_Degree: return False from itertools import zip_longest return all([a==b for a,b in zip_longest(self.Poly,other.Poly,fillvalue=0)]) #+,- def __pos__(self): return self def __neg__(self): return self.scale(-1) #Boole def __bool__(self): return any(self.Poly) #簡略化 def reduce(self): P_deg=self.degree() if not(P_deg>=0): self.Poly=[0] self.censor(self.Max_Degree) return for i in range(self.degree(),-1,-1): if self.Poly[i]: self.Poly=self.Poly[:i+1] self.censor(self.Max_Degree) return self.Poly=[] return #シフト def __lshift__(self,other): if other<0: return self>>(-other) if other>self.Max_Degree: return Modulo_Polynominal([0],self.Max_Degree,self.Char) G=[0]*other+self.Poly return Modulo_Polynominal(G,self.Max_Degree,self.Char) def __rshift__(self,other): if other<0: return self<<(-other) return Modulo_Polynominal(self.Poly[other:],self.Max_Degree,self.Char) #次数 def degree(self): d=len(self.Poly)-1 for y in self.Poly[::-1]: if y: return d d-=1 return -float("inf") #加法 def __add__(self,other): P=self Q=other if Q.__class__==Modulo_Polynominal: from itertools import zip_longest N=min(P.Max_Degree,Q.Max_Degree) R=[(a+b)%Mod for (a,b) in zip_longest(P.Poly,Q.Poly,fillvalue=0)] return Modulo_Polynominal(R,N,P.Char) else: P_deg=P.degree() if P_deg<0:P_deg=0 R=[0]*(P_deg+1) R=[p for p in P.Poly] R[0]=(R[0]+Q)%Mod R=Modulo_Polynominal(R,P.Max_Degree,P.Char) R.reduce() return R def __radd__(self,other): return self+other #減法 def __sub__(self,other): return self+(-other) def __rsub__(self,other): return (-self)+other #乗法 def __mul__(self,other): P=self Q=other if Q.__class__==Modulo_Polynominal: a=b=0 for x in P.Poly: if x: a+=1 for y in Q.Poly: if y: b+=1 if a>b: P,Q=Q,P P.reduce();Q.reduce() U,V=P.Poly,Q.Poly M=min(P.Max_Degree,Q.Max_Degree) if a<2*P.Max_Degree.bit_length(): B=[0]*(len(U)+len(V)-1) for i in range(len(U)): if U[i]: for j in range(len(V)): B[i+j]+=U[i]*V[j] if B[i+j]>Mod: B[i+j]-=Mod else: B=Convolution_Mod(U,V)[:M] B=Modulo_Polynominal(B,M,self.Char) B.reduce() return B else: return self.scale(other) def __rmul__(self,other): return self.scale(other) #除法 def __floordiv__(self,other): if not other: raise ZeroDivisionError if isinstance(other,int): return self/other F,G=self,other N=min(F.Max_Degree,G.Max_Degree) F_deg=F.degree() G_deg=G.degree() if F_deg0: if m&1: A*=Q m>>=1 Q*=Q if n>=0: return A else: return A.__inv__() else: P=Log(self) return Exp(P*other) #逆元 def __inv__(self,deg=None): assert self.Poly[0],"定数項が0" P=self if len(P.Poly)<=P.Max_Degree.bit_length(): """ 愚直に漸化式を用いて求める. 計算量:Pの次数をK, 求めたい項の個数をNとして, O(NK) """ F=P.Poly c=F[0] c_inv=pow(c,Mod-2,Mod) N=len(P.Poly) R=[-c_inv*a%Mod for a in F[1:]][::-1] G=[0]*P.Max_Degree G[0]=1 Q=[0]*(N-2)+[1] for k in range(1,P.Max_Degree): a=0 for x,y in zip(Q,R): a+=x*y a%=Mod G[k]=a Q.append(a) Q=Q[1:] G=[c_inv*g%Mod for g in G] return Modulo_Polynominal(G,P.Max_Degree,P.Char) else: """ FFTの理論を応用して求める. 計算量:求めたい項の個数をNとして, O(N log N) """ if deg==None: deg=P.Max_Degree else: deg=min(deg,P.Max_Degree) F=P.Poly N=len(F) r=pow(F[0],Mod-2,Mod) m=1 G=[r] while mn: E=P.Poly[:n] else: E=P.Poly+[0]*(n-P.Poly) return Modulo_Polynominal(E,P.Max_Degree,P.Char) else: if len(P.Poly)>n: del P.Poly[n:] else: P.Poly+=[0]*(n-len(P.Poly)) #================================================= def Primitive_Root(p): """Z/pZ上の原始根を見つける p:素数 """ 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>e S=[pow(primitive,(Mod-1)>>i,Mod) for i in range(e+1)] for l in range(H, 0, -1): d = 1 << l - 1 U = [1]*(d+1) u = 1 for i in range(d): u=u*S[l]%Mod U[i+1]=u for i in range(1 <>e inv_primitive=pow(primitive,Mod-2,Mod) S=[pow(inv_primitive,(Mod-1)>>i,Mod) for i in range(e+1)] for l in range(1, H + 1): d = 1 << l - 1 for i in range(1 << H - l): u = 1 for j in range(2*i*d, (2*i+1)*d): A[j+d] *= u A[j], A[j+d] = (A[j] + A[j+d]) % Mod, (A[j] - A[j+d]) % Mod u = u * S[l] % Mod N_inv=pow(N,Mod-2,Mod) for i in range(N): A[i]=A[i]*N_inv%Mod #参考元 https://atcoder.jp/contests/practice2/submissions/16789717 def Convolution_Mod(A,B): """A,BをMod を法とする畳み込みを求める. ※Modはグローバル変数から指定 """ if not A or not B: return [] N=len(A) M=len(B) L=N+M-1 if min(N,M)<=50: if N1: E=Convolution_Mod(F,Autocorrelation_Mod(G)[:m])[:m] G=[(2*a-b)%Mod for a,b in zip_longest(G,E,fillvalue=0)] #2.b', 2.c' C=Convolution_Mod(F,dH[:m-1]) R=[0]*m for i,a in enumerate(C): R[i%m]+=a R=[a%Mod for a in R] #2.d' dF=[(k*a)%Mod for k,a in enumerate(F[1:],1)] D=[0]+[(a-b)%Mod for a,b in zip_longest(dF,R,fillvalue=0)] S=[0]*m for i,a in enumerate(D): S[i%m]+=a S=[a%Mod for a in S] #2.e' T=Convolution_Mod(G,S)[:m] #2.f' E=[0]*(m-1)+T E=[0]+[(Inv[k]*a)%Mod for k,a in enumerate(E,1)] U=[(a-b)%Mod for a,b in zip_longest(H[:2*m],E,fillvalue=0)][m:] #2.g' V=Convolution_Mod(F,U)[:m] #2.h' F+=V #2.i' m<<=1 return Modulo_Polynominal(F[:N],P.Max_Degree,P.Char) def Power(P,k): assert k>=0 N=P.Max_Degree F=P.Poly F+=[0]*(N-len(F)) for (d,p) in enumerate(F): if p: break else: return Modulo_Polynominal([0],P.Max_Degree,P.Char) if d*k>P.Max_Degree: return Modulo_Polynominal([0],P.Max_Degree,P.Char) p_inv=pow(p,Mod-2,Mod) Q=Modulo_Polynominal([(p_inv*a)%Mod for a in F[d:]],P.Max_Degree,P.Char) G=Exp(k*Log(Q)).Poly pk=pow(p,k,Mod) G=[0]*(d*k)+[(pk*a)%Mod for a in G] return Modulo_Polynominal(G,P.Max_Degree,P.Char) #================================================ def floating_degree(P): T=P.Poly for i in range(len(T)): if T[i]: return i #================================================ import sys from collections import defaultdict input=sys.stdin.readline write=sys.stdout.write N,Q=map(int,input().split()) M=3000 Mod=998244353 Poly=defaultdict(lambda :Modulo_Polynominal([1]*(M+1),M+1)) X=Modulo_Polynominal([0,1],M+1) V=1/Power(1-X,N+1) Z=[0]*Q for i in range(Q): K,A,B,S,T=map(int,input().split()) P=Poly[K] #P=0 のときを例外処理 if not P: Z[i]=0 continue d=floating_degree(P) V/=(P>>d) V<<=d for j in range(A,B+1): P.Poly[j]=0 V*=P if S==0: Z[i]=V.coefficient(T) else: Z[i]=V.coefficient(T)-V.coefficient(S-1) Z[i]%=Mod write("\n".join(map(str,Z)))