维护左子树右子树的贡献和跨区间贡献
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn=10000000;
const LL inf=2147483646;
const LL MOD=998244353;
#define md(x) (x=(x>MOD)?x-MOD:x)
#define ctwo(x) ((x*(x-1)/2+x)%MOD)
#define dec(x) (x=x?x-1:MOD-1)
#define inc(x) (x=(x==MOD-1)?0:x+1)
inline LL Read(){
LL x=0,f=1; char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1; c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+c-'0'; c=getchar();
}return x*f;
}
struct node{
LL son[2],pre,suf,ans,flag;
}tree[maxn];
LL n,m,nod,root;
inline void mg(node& now,const node& son0,const node& son1){
now.pre=son0.pre+son0.flag*son1.pre;
md(now.pre);
now.suf=son1.suf+son1.flag*son0.suf;
md(now.suf);
now.ans=(son0.ans+son1.ans+son0.suf*son1.pre)%MOD;
if(now.flag){
if(!(son0.flag&&son1.flag))
inc(now.pre),
inc(now.suf),
inc(now.ans);
}
else if(son0.flag&&son1.flag)
dec(now.pre),
dec(now.suf),
dec(now.ans);
}
inline void Update(LL now,LL son0,LL son1,LL len1,LL len2){
if(len1==0){
tree[now].flag=tree[now].pre=tree[now].suf=tree[now].ans=0;
return;
}
node c1,c2;
if(son0)
c1=tree[son0];
else{
len1=len1%MOD,
c1.ans=ctwo(len1),
c1.pre=len1,
c1.suf=len1,
c1.flag=1;
}
if(son1)
c2=tree[son1];
else{
len2=len2%MOD,
c2.ans=ctwo(len2),
c2.pre=len2,
c2.suf=len2,
c2.flag=1;
}
mg(tree[now],c1,c2);
}
inline void Change(LL now,LL l,LL r,LL lt,LL rt){
if(lt==l&&rt==r){
tree[now].flag=0,
Update(now,tree[now].son[0],tree[now].son[1],(r-l)>>1,(r-l+1)>>1);
return;
}
LL mid=(l+r)>>1;
if(mid>lt){
if(!tree[now].son[0]){
tree[now].son[0]=++nod;
LL len=(mid-l)%MOD,son0=nod;
tree[son0].ans=ctwo(len),
tree[son0].pre=len,
tree[son0].suf=len,
tree[son0].flag=1;
}
Change(tree[now].son[0],l,mid,lt,min(rt,mid));
}
if(mid<rt){
if(!tree[now].son[1]){
tree[now].son[1]=++nod;
LL len=(r-mid)%MOD,son1=nod;
tree[son1].ans=ctwo(len),
tree[son1].pre=len,
tree[son1].suf=len,
tree[son1].flag=1;
}
Change(tree[now].son[1],mid,r,max(lt,mid),rt);
}
Update(now,tree[now].son[0],tree[now].son[1],mid-l,r-mid);
}
int main(){
n=Read(),m=Read();
LL len=n%MOD;
root=nod=1,
tree[root].ans=ctwo(len),
tree[root].pre=len,
tree[root].suf=len,
tree[root].flag=1;
while(m--){
LL l=Read(),r=Read();
Change(root,0,n,l-1,r);
}
printf("%lld",tree[root].ans);
return 0;
}