from cmath import inf from re import M import sys from collections import deque, Counter from math import atan2, gcd, log10, pi, sqrt, ceil from bisect import bisect, bisect_left, bisect_right, insort from typing import Iterable, TypeVar, Union, Tuple, Iterator, List # import bisect from decimal import * import fractions import time import copy import heapq import itertools import bisect import math import random from fractions import Fraction from functools import lru_cache, partial, cmp_to_key import operator # import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') # import string # import networkx as nx input = sys.stdin.readline sys.setrecursionlimit(10000000) mod = 10 ** 9 + 7 mod2 = 998244353 # mod = 1 << 128 # mod = 10 ** 30 + 1 INF = 1 << 61 DIFF = 10 ** -9 DX = [1, 0, -1, 0, 1, 1, -1, -1] DY = [0, 1, 0, -1, 1, -1, 1, -1] def read_values(): return map(int, input().split()) def read_index(): return map(lambda x: int(x) - 1, input().split()) def read_list(): return list(read_values()) def read_lists(N): return [read_list() for _ in range(N)] class UnionFind: def __init__(self,n): self.parent=list(range(n)) self.size=[1]*n def root(self,a): if(self.parent[a]==a):return a self.parent[a]=self.root(self.parent[a]) return self.parent[a] def union(self,a,b): pa=self.root(a) pb=self.root(b) if(pa==pb):return if(self.size[pa]>self.size[pb]):pa,pb=pb,pa self.parent[pa] = pb self.size[pb]+=self.size[pa] def same(self,a,b): return self.root(a)==self.root(b) class Dijkstra: def __init__(self,n): self.dist=[inf]*n self.g = [list() for _ in range(n)] def add(self,u,v,c): self.g[u].append((v,c)) def calc(self,s): self.dist[s]=0 q = [(0,s)] while(len(q)>0): d,v0 = heapq.heappop(q) if(d>self.dist[v0]):continue for (v1,c) in self.g[v0]: if(self.dist[v1]<=d+c):continue self.dist[v1]=d+c heapq.heappush(q,(self.dist[v1],v1)) class SegTree: def __init__(self,n): self.size=1 while(self.size1): p=i//2 self.d[p]=self.calc(self.d[p*2],self.d[p*2+1]) i=p #[l,r) def get(self,i): return self.d[self.size+i] def query(self,l,r): return self.queryImpl(l,r,0,self.size,1) def queryImpl(self,l,r,ll,rr,v): if(r<=ll or rr<=l): return self.unit() if(l<=ll and rr<=r): return self.d[v] m = (ll+rr)//2 vl = self.queryImpl(l,r,ll,m,v*2+0) vr =self.queryImpl(l,r,m,rr,v*2+1) return self.calc(vl,vr) class LazySegTree: def __init__(self,n): self.size=1 while(self.size1): p=i//2 self.d[p]=self.calc(self.d[p*2],self.d[p*2+1]) i=p #[l,r) def get(self,i): return self.query(i,i+1) def query(self,l,r): return self.queryImpl(l,r,0,self.size,1) def queryImpl(self,l,r,ll,rr,v): if(r<=ll or rr<=l): return self.unit() self.func(v) if(l<=ll and rr<=r): return self.d[v] m = (ll+rr)//2 return self.calc(self.queryImpl(l,r,ll,m,v*2+0),self.queryImpl(l,r,m,rr,v*2+1)) def funcSet(self,l,r,fnc): return self.funcSetImpl(l,r,fnc,0,self.size,1) def funcSetImpl(self,l,r,fnc,ll,rr,v): if(r<=ll or rr<=l): return if(l<=ll and rr<=r): self.comp(v,fnc) self.func(v) self.forceset(v,self.d[v]) return m = (ll+rr)//2 self.funcSetImpl(l,r,fnc,ll,m,v*2+0) self.funcSetImpl(l,r,fnc,m,rr,v*2+1) def func(self,i): if(i0): r+=self.b[k-1] k-=k&-k return r class MaxFlow: def __init__(self,n): self.g = [list() for _ in range(n)] self.r = [list() for _ in range(n)] self.f = [list() for _ in range(n)] self.mc=[False]*n self.size=n self.q=[-1]*n self.e=0 def add(self,u,v,c): self.g[u].append(v) self.g[v].append(u) self.r[u].append(len(self.f[v])) self.r[v].append(len(self.f[u])) self.f[u].append(c) self.f[v].append(0) self.e+=1 def bfs(self,s,t): self.depth=[-2]*self.size self.depth[s]=0 self.q[0]=s l=0 r=1 while(l0): self.depth[v2]=self.depth[v]+1 if(v2==t):return self.q[r]=v2 r+=1 def dfs(self,v,t,f): if(v==t):return f r=0 for i in range(self.pg[v],len(self.g[v])): self.pg[v]=i v2=self.g[v][i] i2=self.r[v][i] if(self.f[v][i]==0 or self.depth[v]+1!=self.depth[v2]):continue d=self.dfs(v2,t,min(f-r,self.f[v][i])) if(d==0):continue self.f[v][i]-=d self.f[v2][i2]+=d r+=d if(r==f):break self.depth[v]=self.size return r def flow(self,s,t): r=0 while(1): self.bfs(s,t) if(self.depth[t]==-2):return r if(self.depth[t]*self.depth[t]*2>self.e):break self.pg=[0]*self.size f = self.dfs(s,t,10**18) if(f==0):break r+=f while(1): self.fi=[False]*self.size f = self.dfs2(s,t,10**18) if(f==0):break r+=f return r def mincut(self,v): self.mc[v]=True for i in range(len(self.g[v])): v2,c,i2=self.g[v][i] if(self.mc[v2] or self.f[v][i]==0):continue self.mincut(v2) def extgcd(a,b): if(b==0):return (1,0) u,v=extgcd(b,a%b) return (v,u-a//b*v) def convolution(f,g,m): l=1 v=m-1 r=v pg=3 if (m == 2):pg = 1; if (m == 754974721):pg=11; rpg=pow(pg,m-2,m) p=list() rp=list() while(len(f)+len(g)>l+1): l*=2 r//=2 p.append(pow(pg,r,m)) rp.append(pow(rpg,r,m)) while(p[-1]!=1): p.append(p[-1]*p[-1]%m) rp.append(rp[-1]*rp[-1]%m) def FFT(ff,k,pl): fl=len(ff) if(fl==1): return ff hl=fl//2 ef=FFT(ff[::2],k+1,pl) of=FFT(ff[1::2],k+1,pl) r=[0]*fl mul=1 for i in range(hl): r[i+0]=(ef[i]+of[i]*mul)%m r[i+hl]=(ef[i]-of[i]*mul)%m mul=(mul*pl[k])%m return r ff=[0]*l gg=[0]*l for i in range(len(f)): ff[i]=f[i] for i in range(len(g)): gg[i]=g[i] ff=FFT(ff,0,p) gg=FFT(gg,0,p) for i in range(l): ff[i]=(ff[i]*gg[i])%m a=FFT(ff,0,rp) rl=pow(l,m-2,m) for i in range(l): a[i]=a[i]*rl%m return a class scc: def __init__(self,n): self.g=[list() for _ in range(n)] self.rg=[list() for _ in range(n)] self.size=n def add(self,u,v): self.g[u].append(v) self.rg[v].append(u) def calc(self): f=[-1]*self.size nf=[0] c=[False]*self.size def dfs1(v): c[v]=True for tv in self.g[v]: if(c[tv]):continue dfs1(tv) f[nf[0]]=v nf[0]+=1 for i in range(self.size): if(f[i]!=-1):continue dfs1(i) r=list() c=[False]*self.size nf[0]=0 def dfs2(v): r[nf[0]].append(v) c[v]=True for tv in self.rg[v]: if(c[v]):continue dfs1(tv) for i in range(self.size-1,-1,-1): if(c[i]):continue r.append(list()) dfs2(i) nf[0]+=1 return r def lower_bound(a,v): l=-1 r=len(a) while(l+1=r):break v=q[l] for w in self.g[v]: if(fr[w]!=-1): if(d[fr[w]]==0): d[fr[w]]=1 rev[fr[w]]=v q[r]=fr[w] r+=1 else: r=0 vv=v bw=w for _ in p: if(bw==-1):break bw,self.to[vv]=self.to[vv],bw fr[self.to[vv]]=vv vv=rev[vv] break def main(): n,m=read_values() g=list() for v in range(m): p,k=read_values() p-=1 k-=1 g.append((k,p)) g.sort() g.reverse() bi=BIT(n) mod = 998244353 factb=1 for v in range(1,n-m): factb*=v factb%=mod fact=factb*(n-m)%mod half=(mod+1)//2 hoka=(n-m)*(n-m-1)*half%mod hoka*=fact hoka%=mod hoka*=half hoka%=mod ans=hoka%mod for k,p in g: q=bi.query(p) ans+=q*fact ans%=mod bi.update(p,1) cnt=0 for k,p in g: low=p - bi.query(p) + 1 pntl=n-1-k-cnt ans+=pntl*low*factb high=n-m-low pnth=n-m-pntl ans+=pnth*high*factb ans%=mod cnt+=1 print(ans%mod) if __name__ == "__main__": main()