import sys, time, random from collections import deque, Counter, defaultdict input = lambda: sys.stdin.readline().rstrip() ii = lambda: int(input()) mi = lambda: map(int, input().split()) li = lambda: list(mi()) inf = 2 ** 63 - 1 mod = 998244353 class Calculator: 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 def Add(self, A, B): """ 必要ならば末尾に元を追加して, [A[i]+B[i]] を求める. """ if type(A)==int: A=[A] if type(B)==int: B=[B] m=min(len(A), len(B)) C=[(A[i]+B[i])%Mod for i in range(m)] C.extend(A[m:]) C.extend(B[m:]) return C def Sub(self, A, B): """ 必要ならば末尾に元を追加して, [A[i]-B[i]] を求める. """ if type(A)==int: A=[A] if type(B)==int: B=[B] m=min(len(A), len(B)) C=[0]*m C=[(A[i]-B[i])%Mod for i in range(m)] C.extend(A[m:]) C.extend([-b%Mod for b in B[m:]]) return C def Times(self,A, k): """ [k*A[i]] を求める. """ return [k*a%Mod for a in A] #参考元 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: i=Q.popleft(); j=Q.popleft() A[i]=self.Convolution(A[i], A[j]) Q.append(i) i=Q.popleft() return A[i] def Inverse(self, F, length=None): if length==None: M=len(F) else: M=length if M<=0: return [] if self.is_sparse(F): """ 愚直に漸化式を用いて求める. 計算量: F にある係数が非零の項の個数を K, 求める最大次数を N として, O(NK) 時間 """ d,f=self.coefficients_list(F) G=[0]*M alpha=pow(F[0], Mod-2, Mod) G[0]=alpha for i in range(1, M): for j in range(1, len(d)): if d[j]<=i: G[i]+=f[j]*G[i-d[j]]%Mod else: break G[i]%=Mod G[i]=(-alpha*G[i])%Mod del G[M:] else: """ FFTの理論を応用して求める. 計算量: 求めたい項の個数をNとして, O(N log N) Reference: https://judge.yosupo.jp/submission/42413 """ N=len(F) r=pow(F[0],Mod-2,Mod) m=1 G=[r] while m n: return 0 if k == 0 or k == n: return 1 k = min(k, n - k) return (((self.facs[n] * self.factinvs[k]) % self.mod) * self.factinvs[n-k]) % self.mod def perm(self, n, k): return (self.choose(n, k) * self.facs[k]) % self.mod def homop(self, n, k): if n == k == 0: return 1 return self.choose(n + k - 1, k) Mod = mod Calc = Calculator() n, m = mi() C = Combinatorics(mod, 25* 10 ** 5 + 2) a = [] for _ in range(m): l, r = mi() a.append(r - l + 1) A = [] cat = [0] * (2 * n + 3) for i in range(1, n + 1): cat[2 * i] = C.choose(2 * i, i) * pow(i + 1, -1, mod) % mod for v in a: now = [0] * (v + 1) now[0] = 1 now[v] = -cat[v] A.append(now) C = Calc.Multiple_Convolution(A)[0] C += [0] * (n + 1 - len(C)) ans = 0 cat[0] = 1 for i in range(n + 1): ans += C[i] * cat[n - i] % mod ans %= mod print(ans)